D. Реалити-шоу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Одно известное реалити-шоу набирает участников для третьего сезона! Собеседование прошли $$$n$$$ кандидатов, пронумерованных от $$$1$$$ до $$$n$$$. $$$i$$$-й кандидат обладает агрессивностью $$$l_i$$$, и для того, чтобы взять этого кандидата, организаторам шоу придется потратить $$$s_i$$$ рублей.

Ведущая реалити-шоу листает досье всех кандидатов от $$$i=1$$$ до $$$i=n$$$ в порядке возрастания номеров, и для каждого из них она принимает решение, стоит ли взять этого кандидата в шоу. Если агрессивность кандидата $$$i$$$ строго выше, чем агрессивность какого-либо из уже взятых кандидатов, то кандидата $$$i$$$ она точно брать откажется. В противном случае ведущая может на свой выбор как взять кандидата в шоу, так и не взять. Ведущая хочет выбрать участников таким образом, чтобы максимизировать прибыль.

Рассматриваемое реалити-шоу получает доход следующим образом. Для каждого значения агрессивности $$$v$$$ указана доходность $$$c_v$$$, которая может быть как положительной, так и отрицательной. Участники, попавшие в проект, поочередно выходят на сцену в порядке возрастания номеров. Как только участник с номером $$$i$$$ выходит на сцену, происходит следующее:

  • Шоу зарабатывает $$$c_{l_i}$$$ рублей, где $$$l_i$$$ — изначальная агрессивность участника $$$i$$$.
  • Если оказывается, что на сцене находятся два участника с одинаковым значением агрессивности, то они немедленно начинают драку. В результате драке происходит следующее:
    • проигравшего участника увозит скорая помощь, и он выбывает из проекта,
    • агрессивность выигравшего участника возрастает на один, а шоу зарабатывает $$$c_t$$$ рублей, где $$$t$$$ — новое значение агрессивности.
  • Драки на сцене продолжаются до тех пор, пока на сцене не останутся участники с различными значениями агрессивности.

Ведущая шоу хочет выбрать команду таким образом, чтобы максимизировать прибыль, которая определяется как суммарный доход от происходящего на сцене, минус суммарные затраты на приглашение участников (которые определяются как сумма $$$s_i$$$ для выбранных участников). Помогите ведущей сделать шоу максимально прибыльным!

Входные данные

В первой строке вводится два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2000$$$) — количество кандидатов и максимальное начальное значение агрессивности кандидатов.

Во второй строке вводится $$$n$$$ целых чисел $$$l_i$$$ ($$$1 \le l_i \le m$$$) — агрессивность каждого из кандидатов.

В третьей строке вводится $$$n$$$ целых чисел $$$s_i$$$ ($$$0 \le s_i \le 5000$$$) — количество рублей, которое придется заплатить для найма каждого из кандидатов.

В четвертой строке вводится $$$n + m$$$ целых чисел $$$c_i$$$ ($$$|c_i| \le 5000$$$) — уровень доходности для каждого из значений агрессивности.

Гарантируется, что при данных ограничениях значение агрессивности участников не может превысить $$$n + m$$$.

Выходные данные

Выведите одно целое число — максимальную прибыль шоу.

Примеры
Входные данные
5 4
4 3 1 2 1
1 2 1 2 1
1 2 3 4 5 6 7 8 9
Выходные данные
6
Входные данные
2 2
1 2
0 0
2 1 -100 -100
Выходные данные
2
Входные данные
5 4
4 3 2 1 1
0 2 6 7 4
12 12 12 6 -3 -5 3 10 -4
Выходные данные
62
Примечание

В первом примере выгоднее всего взять кандидатов с номерами $$$1, 2, 3, 5$$$. В таком случае шоу заплатит им за участие $$$1 + 2 + 1 + 1 = 5$$$ рублей. На сцене же будет происходить следующее:

  • на сцене появится участник со значением агрессивности $$$4$$$, шоу заработает $$$4$$$ рубля;
  • на сцене появится участник со значением агрессивности $$$3$$$, шоу заработает $$$3$$$ рубля;
  • на сцене появится участник со значением агрессивности $$$1$$$, шоу заработает $$$1$$$ рубль;
  • на сцене появится еще один участник со значением агрессивности $$$1$$$, шоу заработает еще $$$1$$$ рубль, начнется драка. Один из участников проиграет и покинет проект, а второй повысит свое значение агрессивности до $$$2$$$. Шоу заработает на этом еще $$$2$$$ рубля.

Таким образом, доход шоу составит $$$4 + 3 + 1 + 1 + 2=11$$$ рублей, а суммарная прибыль будет равна $$$11 - 5 = 6$$$ рублям.

Во втором примере мы не можем пригласить обоих кандидатов, так как значение агрессивности второго кандидата больше, поэтому нам выгоднее взять кандидата с номером $$$1$$$.