F. Грузовики и города
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вдоль дороги, которую можно представить как прямую линию, расположены $$$n$$$ городов. $$$i$$$-й город находится на расстоянии $$$a_i$$$ километров от начала координат. Все города расположены по одну сторону от начала координат. Также есть $$$m$$$ грузовиков, курсирующих между городами.

Каждый грузовик может быть описан $$$4$$$-мя числами: начальный город $$$s_i$$$, конечный город $$$f_i$$$, расход топлива $$$c_i$$$ и количество возможных дозаправок $$$r_i$$$. $$$i$$$-й грузовик тратит $$$c_i$$$ литров топлива на один километр.

Когда грузовик приезжает в некоторый город, он может дозаправиться в нем (но дозаправляться можно только в городах). $$$i$$$-й грузовик может быть дозаправлен не более чем $$$r_i$$$ раз. При дозаправке грузовик набирает полный бак. Все грузовики стартуют из своих городов с полным баком.

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

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 400$$$, $$$1 \le m \le 250000$$$) — количество городов и грузовиков соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i < a_{i+1}$$$) — позиции городов с возрастающем порядке.

Следующие $$$m$$$ строк содержат по $$$4$$$ целых числа каждая. $$$i$$$-я строка содержит целые числа $$$s_i$$$, $$$f_i$$$, $$$c_i$$$, $$$r_i$$$ ($$$1 \le s_i < f_i \le n$$$, $$$1 \le c_i \le 10^9$$$, $$$0 \le r_i \le n$$$) — описание $$$i$$$-го грузовика.

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

Выведите единственное число — минимально возможный объем топливных баков $$$V$$$ такой, что все грузовики смогут достигнуть своих конечных городов.

Пример
Входные данные
7 6
2 5 7 10 14 15 17
1 3 10 0
1 7 12 7
4 5 13 3
4 7 10 1
4 7 10 1
1 5 11 2
Выходные данные
55
Примечание

Рассмотрим запросы поподробнее:

  1. $$$1$$$-й грузовик должен прибыть в позицию $$$7$$$ из $$$2$$$ без дозаправок, поэтому ему необходим бензобак объема хотя бы $$$50$$$.
  2. $$$2$$$-й грузовик должен прибыть в позицию $$$17$$$ из $$$2$$$ и может дозаправляться в каждом городе вдоль пути (который находится между начальным и конечным городом), поэтому ему необходим бак объема хотя бы $$$48$$$.
  3. $$$3$$$-й грузовик должен прибыть в позицию $$$14$$$ из $$$10$$$, так как нет городов между позициями, то грузовику необходим бак объема хотя бы $$$52$$$.
  4. $$$4$$$-й грузовик должен прибыть в позицию $$$17$$$ из $$$10$$$ и может дозаправиться один раз: оптимально дозаправиться в $$$5$$$-м городе (позиция $$$14$$$), поэтому ему необходим бак объема хотя бы $$$40$$$.
  5. $$$5$$$-й грузовик имеет то же самое описание, поэтому ему также понадобится бак объема хотя бы $$$40$$$.
  6. $$$6$$$-th грузовик должен прибыть в позицию $$$14$$$ из $$$2$$$ и может дозаправиться два раза: первый раз в городе $$$2$$$ или $$$3$$$ и второй раз в городе $$$4$$$, поэтому ему понадобится бак объема хотя бы $$$55$$$.