Задача №114890. Гонка
Совсем недавно компания «Memtendo» выпустила новую версию культовой игры «Super Mario Kart»! В новой версии игры, как и в оригинальной, герои участвуют в гонках на машинах.
Всего в игре есть n персонажей, пронумерованных целыми числами от 1 до n . Перед выпуском игры разработчики провели опрос фанатов, и выяснили, насколько они любят каждого из персонажей. По итогам опроса для каждого персонажа была выявлена его популярность — целое неотрицательное число. Популярность i -го персонажа равна b i .
Каждая игра состоит из нескольких заездов, в каждом из которых принимают участие все персонажи. По итогам каждого заезда лучшие k персонажей получают некоторое количество баллов в общий зачет. А именно, персонаж, финишировавший первым, получает a 1 баллов, персонаж, финишировавший вторым, получает a 2 баллов, и так далее. Персонаж, финишировавший k -м, получает a k баллов в общий зачет. Все остальные персонажи получают 0 баллов в общий зачет по итогам заезда. Благодаря современным технологиям, время финиша измеряется абсолютно точно, а потому можно считать, что никакие два персонажа не финишируют одновременно. Также, исходя из принципа справедливого распределения баллов, выполняется неравенство a 1 > a 2 > ... > a k > 0 .
Для подведения итогов игры для каждого из персонажей вычисляется его общий балл в этой игре. Общий балл персонажа определяется следующим образом: берутся все баллы (в том числе и нулевые), набранные этим персонажем за все заезды, из этих баллов вычеркивается s минимальных значений, а оставшиеся значения складываются и прибавляются к популярности персонажа. Например, если Луиджи обладает популярностью 3 , в четырех заездах он набрал 2 , 1 , 3 и 0 баллов соответственно, а s = 2 , то из баллов, полученных за заезды, будут вычеркнуты два минимальных, то есть 1 и 0 , а общий балл Луиджи будет равен 3 + 2 + 3 = 8 . Итоги игр, в которых было менее s заездов, не подводятся, чтобы избежать неоднозначности трактовки правил.
Во время очередной игры Марио и динозаврик Йоши решили немного пофантазировать. За время игры уже было проведено m заездов, результаты которых Марио и Йоши знают. Пока готовится очередной заезд, герои играют в следующую мини-игру: Йоши называет номера двух различных персонажей u и v , а Марио должен ответить, какое минимальное число заездов нужно ещё провести, чтобы общий балл персонажа v был строго больше общего балла персонажа u . Обратите внимание, что герои лишь фантазируют, а Марио интересует теоретический минимум количества дополнительных звездов, то есть Марио может выбрать самый выгодный для себя исход каждого из дополнительных заездов. Мини-игра показалась Марио довольно скучной, поэтому он просит вас написать программу, которая могла бы играть с Йоши вместо него.
Первая строка входных данных содержит четыре целых числа n , m , k , s — количество персонажей в игре, количество уже проведенных заездов, количество персонажей, которые получают ненулевые баллы в общий зачет по итогам одного заезда, и количество заездов, не учитываемых при подведении итогов игры, соответствено ( 2 ≤ n ≤ 1000 , 1 ≤ m ≤ 1000 , 1 ≤ k ≤ n , 0 ≤ s ≤ min (10, m ) ).
Вторая строка содержит k чисел a 1 , a 2 , ..., a k — баллы, которые получают лучшие k персонажей по итогам каждого заезда ( 1 ≤ a k < a k - 1 < ... < a 2 < a 1 ≤ 10 9 ).
Третья строка содержит n чисел b 1 , b 2 , ..., b n — значения популярности каждого из персонажей ( 0 ≤ b 1 , b 2 , ..., b n ≤ 10 9 ).
Следующие m строк описывают результаты уже состоявшихся заездов. Каждая из них содержит n различных чисел от 1 до n — список номеров персонажей в том порядке, в котором они финишировали в очередном заезде.
Следующая строка содержит единственное целое число q — количество вопросов, заданных Йоши ( 1 ≤ q ≤ 10 5 ).
Каждая из следующих q строк содержит два целых числа u и v — номера персонажей, фигурирующих в очередном вопросе ( 1 ≤ u , v ≤ n , u ≠ v ).
Для каждого вопроса выведите единственное целое число — минимальное количество дополнительных заездов, которое необходимо провести, чтобы была теоретическая возможность того, что у персонажа с номером v общий балл по итогам всех заездов будет больше, чем у персонажа с номером u . Если дополнительных заездов проводить не надо вообще, в качестве ответа на вопрос выведите число 0 .
Гарантируется, что ответ на каждый вопрос существует, то есть всегда имеется теоретическая возможность того, что персонаж с номером v через конечное число дополнительных заездов будет иметь больший общий балл, чем персонаж с номером u .
Эта задача состоит из шести подзадач. Для подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех необходимых подзадач. Необходимые подзадачи также указаны в таблице.
| Ограничения | |||||||
| Подзадача | Баллы | n , m | q | s | b i | a i | Необходимые подзадачи |
| 1 | 12 | n , m ≤ 50 | q ≤ 50 | s = 0 | b i = 0 | a i ≤ 10 5 | – |
| 2 | 14 | n , m ≤ 50 | q ≤ 50 | s ≤ min (10, m ) | b i = 0 | a i ≤ 10 5 | 1 |
| 3 | 15 | n , m ≤ 1000 | q ≤ 1000 | s = 0 | b i = 0 | a i ≤ 10 9 | 1 |
| 4 | 17 | n , m ≤ 1000 | q ≤ 1000 | s ≤ min (10, m ) | b i = 0 | a i ≤ 10 9 | 1, 2, 3 |
| 5 | 20 | n , m ≤ 1000 | q ≤ 10 5 | s = 0 | b i ≤ 10 9 | a i ≤ 10 9 | 1, 3 |
| 6 | 22 | n , m ≤ 1000 | q ≤ 10 5 | s ≤ min (10, m ) | b i ≤ 10 9 | a i ≤ 10 9 | 1, 2, 3, 4, 5 |
4 3 3 1 5 3 2 4 5 2 1 3 4 2 1 3 4 2 1 4 3 2 1 5 1 2 3 2 4 3 4 1 3 1
0 2 0 2 3