| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 30 | 16 | 16 | 53.333% |
Сегодня прадядя Стэн устроил ярмарку с аттракционами. Диппера заинтересовал один аттракцион, но, к сожалению, чтобы на нем прокатиться, нужно сыграть в игру от прадяди и затем отстоять длинную очередь.
Игра (кто вообще придумал ее так назвать?) происходит следующим образом: люди стоят в $n$ колонн (колонны нумеруются слева направо), затем происходят сдвиги. В процессе сдвига последняя колонна, начиная с первого человека, выходит из игры и уходит в очередь к аттракциону, предпоследняя колонна, начиная с первого человека, переходит в последнюю колонну, при этом первый человек становится последним, и так далее, все остальные колонны таким же образом сдвигаются на одну вперед.
Например, вот так произойдет сдвиг для такого расположения людей:
В результате люди с номерами 5ドル$ и 6ドル$ уходят в очередь на аттракцион, а остальные продолжают играть.
Когда новый человек приходит, чтобы участвовать в игре, он становится первым (люди в колонне нумеруются сверху вниз) в самую левую колонну. Сейчас Диппер стоит рядом с левой колонной, а очередь к аттракциону еще пуста. Ровно через $t$ минут произойдет первый сдвиг, а затем они будут происходить спустя каждые $t$ минут. Дитя Времени сообщило Дипперу времена, в которые подойдут все оставшиеся люди, желающие принять участие в игре и прокатиться на аттракционе. Причем никакие два человека не подойдут в одну минуту. Теперь он размышляет, как лучше поступить, чтобы прокатиться на аттракционе раньше всего. А именно, он решил, что пропустит перед собой некоторое, возможно нулевое, количество еще не подошедших людей, и после этого сразу же войдет в игру, то есть встанет в первую колонну. Если он решит никого не пропускать, он встанет в игру прямо сейчас. При этом он хочет, чтобы количество людей, которые прокатятся на аттракционе перед ним, было как можно меньше.
Считайте, что сдвиг происходит мгновенно. Если в одну и ту же минуту подходит человек и происходит сдвиг, человек успевает войти в игру перед сдвигом. При этом Диппер также может войти в игру после этого человека и перед сдвигом.
Помогите Дипперу, выясните, какое минимальное количество человек успеет прокатиться на аттракционе перед ним, и сколько человек он должен для этого пропустить вперед. Если он может пропустить разное количество людей, выведите минимальное из них.
В первой строке находятся три целых числа: $n,ドル $m$ и $t$ --- количество колонн, людей, которые подойдут позже, и время между сдвигами соответственно (1ドル \le n, t \le 100,000円$; 0ドル \le m \le 100,000円$).
Во второй строке содержится $n$ целых чисел $a_i$ --- количество людей в колоннах в текущий момент (0ドル \le a_i \le 100,000円$).
В третьей строке содержится $m$ целых чисел $t_i$ --- количество минут, спустя которые подойдет $i$-й человек (1ドル \le t_i \le 100,000円$; $t_i < t_{i + 1}$).
В единственной строке выведите два числа: минимальное количество человек, которые прокатятся на аттракционе перед Диппером, и количество человек, которых он должен пропустить вперед.
Если ответ не единственен, выведите тот, в котором второе число минимально.
4 3 4 3 0 1 2 1 4 6
6 0