Вы решили проехать по платной дороге, которая состоит из $$$K$$$ полос. Также на этой дороге стоит $$$N + 1$$$ терминал для оплаты проезда (один в начале, другой в конце и остальные посередине дороги). Терминалы нумеруются числами от 1 до $$$N + 1$$$, где 1 — терминал у начала дороги, а $$$N + 1$$$ — терминал у конца дороги.
Вы знаете, что время проезда между терминалом $$$i$$$ и терминалом $$$i + 1$$$ по полосе $$$j$$$ $$$(1 \le i \le N, 1 \le j \le K)$$$ равно $$$A_{i,j}$$$ . Также в любом терминале вы можете сменить полосу, каждое перемещение на соседнюю полосу занимает $$$X$$$ минут. Можно сместится на несколько полос.
Вам нужно найти, за какое минимальное время вы сможете добраться от начала дороги (от любой полосы терминала 1) до конца дороги (любой полосы терминала $$$N + 1$$$).
Кроме этого, в будущем планируется $$$Q$$$ ремонтов, занумерованных от 1 до $$$Q$$$. Нужно определить минимальное время проезда во время ремонтов. Во время ремонта $$$i$$$ по полосе $$$l_i$$$ нельзя проехать между терминалами $$$t_i$$$ и $$$t_i + 1$$$. Ремонты происходят последовательно, одновременно идёт только один ремонт. Обратите внимание, что в некоторых подзадачах $$$Q = 0$$$, то есть ремонтов не будет.
В первой строке вводятся три целых числа $$$N$$$, $$$K$$$ и $$$X$$$ $$$(2 \le N, K \le 10^6, N \cdot K \le 10^6, 1 \le X \le 10^9)$$$ — число терминалов, полос и время смены полосы на соседнюю соответственно. В следующих $$$N$$$ строках содержится по $$$K$$$ целых чисел $$$A_{i,1}$$$, $$$A_{i,2}$$$, $$$A_{i,3}$$$, $$$\dotsc$$$, $$$A_{i,K}$$$ $$$(1 \le A_i,j \le 10^9)$$$ — времена проезда между терминалами.
В следующей строке вводится одно целое число $$$Q$$$ $$$(0 \le Q \le 10^6)$$$ — количество ремонтов. В следующих $$$Q$$$ строчках вводится по два целых числа $$$t_i$$$ и $$$l_i$$$ $$$(1 \le t_i \le N, 1 \le l_i \le K)$$$ — параметры ремонта.
В первой строке выведите минимальное время, за которое вы можете добрать от начала до конца дороги.
В следующих $$$Q$$$ строках — минимальное время, за которое вы можете добрать от начала до конца дороги во время ремонта.
В этой задаче 25 тестов, кроме тестов из условия. Каждый тест оценивается в 4 балла. Тесты можно разделить на следующие группы:
| Номер | Макс. балл | Ограничения | ||
| $$$N$$$ | $$$K$$$ | $$$Q$$$ | ||
| $$$1$$$ | 12 | $$$n \le 10$$$ | $$$K \le 2$$$ | $$$Q = 0$$$ |
| $$$2$$$ | 12 | $$$n \le 10$$$ | $$$K \le 10$$$ | $$$Q = 0$$$ |
| $$$3$$$ | 12 | $$$n \le 100$$$ | $$$K \le 300$$$ | $$$Q = 0$$$ |
| $$$4$$$ | 12 | $$$n \le 100$$$ | $$$K \le 300$$$ | $$$Q \le 100$$$ |
| $$$5$$$ | 12 | $$$n \le 100$$$ | $$$K \le 10^4$$$ | $$$Q = 0$$$ |
| $$$6$$$ | 12 | $$$n \le 10^4$$$ | $$$K \le 300$$$ | $$$Q \le 10^4$$$ |
| $$$7$$$ | 28 | — | — | — |
3 3 2 12 2 10 10 10 4 3 7 8 2 1 1 1 2
15 15 21
3 2 5 20 30 10 5 20 10 6 1 1 1 2 2 1 2 2 3 1 3 2
40 45 40 40 45 40 50
В первом тестовом примере минимальное время достигается следующим образом:
- Путь начинается с полосы номер 2. После этого мы доезжаем до терминала номер 2 тратя на это 2 минуты.
- Далее требуется перейти с полосы номер 2 на полосу с номером 3, затратив на это дополнительно 2 минуты, а время для достижение третьего терминала будет равно 4 минутам. Суммарное время для достижения терминала номер 3 равно $$$2 + 2 + 4 = 8$$$ минут.
- Далее требуется перейти с полосы номер 3 на первую полосу. Для этого потребуется дополнительно $$$2 \cdot 2 + 3 = 7$$$ минут. Суммарное время для достижения последнего терминала — $$$8 + 2 \cdot 2 + 3 = 15$$$ минут.
Ответ на первый запрос — 15 минут, т. к. наш исходный путь не использует полосу номер 1.
Ответ на второй запрос — 21 минута, потому что оптимальный путь теперь начинается с полосы номер 3.
| Name |
|---|