402955: GYM100957 J Игра Пети

Студент МИСиСа Петя также как и Вася любит придумывать разные игры. Вдохновившись творением Васи он придумал свою еще более новую и уникальную игру.

Игра Пети также происходит на прямоугольном поле размера M × N клеток. Будем считать, что левая верхняя клетка имеет координаты (1, 1). Значения во всех клетках изначально равны нулю. В игру играет Q человек. Каждый человек за один ход может выбрать некоторый прямоугольник, стороны которого параллельны сторонам поля, и прибавить ко всем его клеткам некоторое целое число A.

Теперь Петю очень интересует, какое максимальное значение элемента получилось на результирующем поле. Помогите ему в этом.

В первой строке записано единственное целое число 1 ≤ Q ≤ 10⁴ – количество игроков.

В следующих Q строках записаны ходы игроков. Каждая из строк содержит пять целых чисел: Y₁, X₁, Y₂, X₂, A, где (Y₁, X₁) – строка и столбец верхнего левого угла выбранного игроком прямоугольника, а (Y₂, X₂) – строка и столбец нижнего правого угла выбранного игроком прямоугольника. 1 ≤ X₁ ≤ X₂ ≤ N, 1 ≤ Y₁ ≤ Y₂ ≤ M.  - 100 ≤ A ≤ 100 – число, которое должно быть прибавлено в каждой клетке выбранного прямоугольника.

В (Q + 2)-й строке записаны два числа M и N, 5 ≤ M ≤ 10⁹, 5 ≤ N ≤ 4000 – высота и ширина поля.

Выведите ровно одно целое число – максимальное значение элемента матрицы после ходов всех Q игроков.

2
2 4 6 8 1
4 5 9 9 3
10 10

4