Спустя годы поисков, разочарований и приключений кладоискатели нашли легендарную пещеру, где должен был быть зарыт огромный клад. Однако здесь они не нашли сокровище, а лишь $$$k$$$ ключей от сундуков и загадочное послание. Оказалось, что клад зарыт в $$$n$$$ различных городах, которые соединяет одна быстрая река. Причём в городе $$$i$$$ спрятано $$$a_i$$$ монет.
В данный момент кладоискатели находятся в городе $$$1$$$. Для того чтобы перемещаться между городами, они будут подниматься вверх по реке на своём корабле. Однако им придётся платить $$$c_i$$$ монет на закупку угля, чтобы из города $$$i$$$ добраться до города $$$i+1$$$ – других путей между городами нет.
Кладоискатели в сумме могут открыть не более $$$k$$$ сундуков, но если они приезжают в город $$$i$$$, они не обязательно будут тратить свой ключ на клад здесь. После того как они прекратят поиски сокровища, они смогут поехать обратно без затрат на уголь(можно считать, что спуск вниз по этой реке не требует топлива).
Необходимо определить, какую максимальную прибыль они смогут получить.
В первой строке содержатся два целых числа $$$n, k\, (1 \le k \le n \le 10^5)$$$.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n\, (0 \le a_i \le 10^9)$$$ – количество монет в каждом городе.
Во третьей строке содержатся $$$n - 1$$$ целых числа $$$с_1, с_2, \ldots, с_{n-1}, (0 \le c_i \le 10^9)$$$ – стоимости перемещения из города $$$i$$$ в город $$$i+1$$$.
Выведите максимально возможную прибыль.
5 210 3 2 20 455 5 5 50
15
7 30 0 5 8 13 17 209 5 7 10 1 8
10
| Весенний кубок МИФИ 2025 |
|---|
| Закончено |
