Вдоль дороги, которую можно представить как прямую линию, расположены \(n\) городов. \(i\)-й город находится на расстоянии \(a_i\) километров от начала координат. Все города расположены по одну сторону от начала координат. Также есть \(m\) грузовиков, курсирующих между городами.
Каждый грузовик может быть описан \(4\)-мя числами: начальный город \(s_i\), конечный город \(f_i\), расход топлива \(c_i\) и количество возможных дозаправок \(r_i\). \(i\)-й грузовик тратит \(c_i\) литров топлива на один километр.
Когда грузовик приезжает в некоторый город, он может дозаправиться в нем (но дозаправляться можно только в городах). \(i\)-й грузовик может быть дозаправлен не более чем \(r_i\) раз. При дозаправке грузовик набирает полный бак. Все грузовики стартуют из своих городов с полным баком.
Все грузовики будут оснащены топливными баками одинакового объема \(V\) литров. Вам необходимо найти минимально возможное значение \(V\) такое, что все грузовики могут достигнуть своих конечных городов дозаправляясь не более чем разрешенное количество раз.
Выходные данные
Выведите единственное число — минимально возможный объем топливных баков \(V\) такой, что все грузовики смогут достигнуть своих конечных городов.
Примечание
Рассмотрим запросы поподробнее:
- \(1\)-й грузовик должен прибыть в позицию \(7\) из \(2\) без дозаправок, поэтому ему необходим бензобак объема хотя бы \(50\).
- \(2\)-й грузовик должен прибыть в позицию \(17\) из \(2\) и может дозаправляться в каждом городе вдоль пути (который находится между начальным и конечным городом), поэтому ему необходим бак объема хотя бы \(48\).
- \(3\)-й грузовик должен прибыть в позицию \(14\) из \(10\), так как нет городов между позициями, то грузовику необходим бак объема хотя бы \(52\).
- \(4\)-й грузовик должен прибыть в позицию \(17\) из \(10\) и может дозаправиться один раз: оптимально дозаправиться в \(5\)-м городе (позиция \(14\)), поэтому ему необходим бак объема хотя бы \(40\).
- \(5\)-й грузовик имеет то же самое описание, поэтому ему также понадобится бак объема хотя бы \(40\).
- \(6\)-th грузовик должен прибыть в позицию \(14\) из \(2\) и может дозаправиться два раза: первый раз в городе \(2\) или \(3\) и второй раз в городе \(4\), поэтому ему понадобится бак объема хотя бы \(55\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|