H. Бернард и квадратный колобок
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рудольф подарил Бернарду нового электронного питомца, называемого «Квадратный колобок». Квадратный колобок представляет собой прямоугольный параллелепипед бесконечного объема, на одной из граней которого находится прямоугольное отверстие размером $$$H \times W$$$ — рот колобка.

Колобок питается специальной прямоугольной едой, которая продается наборами. Один такой набор шел в комплекте с питомцем. Каждая порция из набора также представляет собой прямоугольный параллелепипед с измерениями $$$P_i$$$, $$$Q_i$$$ и $$$R_i$$$. Колобок может съесть и переварить порцию, если она без сжатий и трансформаций может пройти через рот колобка так, что плоскость грани параллельна плоскости рта колобка, а стороны грани параллельны границам рта колобка. По мере попадания внутрь колобка порция мгновенно трансформируется в бесформенную массу и заполняет внутреннее пространство колобка.

Бернард хочет, чтобы его питомец был всегда максимально сыт. Поэтому он докупил специальный нож, который может выполнить не более $$$K$$$ разрезов порций еды. После выполнения максимального количества разрезов нож изнашивается и больше не пригоден к использованию. Колобок способен усваивать исключительно прямоугольную еду. Поэтому разрезать порции можно только вдоль плоскости, параллельной одной из граней порции.

Теперь Бернард хочет знать, какой максимальный объем еды из имеющегося набора сможет употребить его питомец.

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

Первая строка содержит целые числа $$$H$$$, $$$W$$$ ($$$1 \le H, W \le 10^4$$$) — размеры рта колобка.

Вторая строка содержит целые числа $$$N$$$ и $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$0 \le K \le 2$$$) — количество порций в стартовом наборе колобка и допустимое количество разрезаний, которые можно выполнить имеющимся у Бернарда ножом.

Далее следует $$$N$$$ строк, каждая из которых содержит по три целых числа $$$P_i$$$, $$$Q_i$$$ и $$$R_i$$$ ($$$1 \le P_i, Q_i, R_i \le 10^3$$$) — размеры порций еды.

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

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

Система оценки
ГруппаДоп. ограниченияБаллыТребуемые подзадачиТип проверки
$$$1$$$$$$K = 0, 1 \le N \le 10^3$$$$$$15$$$—Полная
$$$2$$$$$$K \le 1, 1 \le N \le 10^3$$$$$$25$$$$$$1$$$Полная
$$$3$$$$$$K \le 2, 1 \le N \le 10^3$$$$$$40$$$$$$2$$$Полная
$$$4$$$—$$$20$$$$$$3$$$Полная
Примеры
Входные данные
2 3
5 0
1 2 3
2 3 4
3 4 5
4 4 2
1 1 1
Выходные данные
31
Входные данные
2 3
5 1
1 2 3
2 3 4
3 4 5
4 4 2
1 1 1
Выходные данные
91
Примечание

Каждый разрез выполняется на цельном параллелепипеде. Нельзя одновременно одним разрезом разрезать две порции еды, даже если они были частями одной порции.