Очень жаркое лето. Фермер Дон решил купить некоторое количество кондиционеров.
У ФД имеется \(N\) коров (\(1 \leq N \leq 20\)), которые живут в амбаре,
содержащем последовательность стойл, пронумерованные \(1 \ldots 100\). Корова \(i\)
занимает диапазон стойл, начиная с \(s_i\) и заканчивая в \(t_i\). Диапазоны стойл,
занимаемые коровами, не пересекаются. У коров различные требования к охлаждению.
Корова \(i\) должна быть охлаждена на количество \(c_i\). Это значает, что для всех стойл,
занимаемых коровой \(i\) температура должна быть уменьшена на \(c_i\) единиц.
Амбар содержит \(M\) кондиционеров, помеченных \(1 \ldots M\) (\(1 \leq M \leq 10\)).
\(i\)-ый кондиционер стоит \(m_i\) единиц денег, если работает и охлаждает воздух
(уменьшает температуру) в стойлах начиная в \(a_i\) и заканчивая в \(b_i\).
Если работает, \(i\)-ый кондиционер уменьшает температуру во всех стойлах этого
диапазона на величину \(p_i\) (\(1 \leq p_i \leq 10^6\)). Диапазоны стойл кондиционеров
могут перекрываться.
Определите минимальное количество денег, которое ФД должен потратить, чтобы
сделать температуру комфортабельной для всех коров во всех стойлах.
Гарантируется, что это возможно сделать.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит \(N\) и \(M\).
Последующие \(N\) строк описывают коров. \(i\)-ая из этих строк содержит \(s_i\),
\(t_i\), \(c_i\).
Последующие \(M\) строк описывают кондиционеры. \(i\)-ая из этих строк содержит
\(a_i\), \(b_i\), \(p_i\), \(m_i\).
Для всех тестов, кроме тех, что в примере, можете полагать, что \(M = 10\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите одно целое число - минимальное количество денег, которое ФД должен потратить
чтобы сделать комфортабельной температуру для всех коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5
|
10
|