Артём купил себе приставку и решил играть в неё непрерывно в течение $$$x$$$ часов. Сутки в игровом мире состоят из $$$T$$$ часов. Известно расписание изменения стоимости электроэнергии: в моменты времени $$$t_i$$$ ($$$0 \le t_i \lt T$$$) цена за час меняется на $$$c_i$$$.
Необходимо определить минимальную стоимость, которую придётся заплатить Артёму за $$$x$$$ часов игровой сессии, если он может начать в любой момент времени.
Первая строка содержит два целых числа $$$T, x$$$ — продолжительность суток в часах, продолжительность игровой сессии в часах. $$$(1 \le T, X \le 10^9)$$$.
Во второй строке вводится целое число $$$n$$$ — количество моментов изменения цены $$$(1 \le n \le 10^5)$$$.
В третьей строке вводятся $$$n$$$ целых чисел $$$t_i$$$ — моменты изменения цены ($$$0 \le t_i \lt T$$$).
В четвёртой строке вводятся $$$n$$$ целых чисел $$$c_i$$$ — новая стоимость электроэнергии начиная с момента $$$t_i$$$ ($$$1 \le c_i \le 10^9$$$).
Гарантируется, что $$$t_0 = 0$$$, все моменты $$$t_i$$$ различны, а также $$$t_i$$$ отсортированы в порядке возрастания.
Выведите одно целое число — минимальную стоимость электроэнергии за $$$x$$$ часов игровой сессии.
Тесты в этой задаче разбиты на 6 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 9 | $$$T, x \le 100$$$ | — |
| 2 | 5 | $$$x$$$ делится нацело на $$$T$$$ | — |
| 3 | 15 | $$$T, X \le 1000$$$ | 1 |
| 4 | 24 | $$$X \le 10^5$$$ | — |
| 5 | 22 | $$$n \le 1000$$$ | — |
| 6 | 25 | — | 1-5 |
24 530 8 165 3 7
15
100 1020 5010 20
100
12 10040 3 6 92 1 5 3
269
