Дуже спекотне літо. Фермер Дон вирішив купити кілька кондиціонерів.

У ФД є \(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\)). Діапазони стійл кондиціонерів можуть перекриватися.

Визначте мінімальну кількість грошей, яку ФД має витратити, щоб зробити температуру комфортною для всіх корів у всіх стійлах. Гарантується, що це можна зробити.

Формат вхідних даних

Перший рядок містить \(N\) та \(M\).

Наступні \(N\) рядків описують корів. \(i\)-а з цих рядків містить \(s_i\), \(t_i\), \(c_i\).

Наступні \(M\) рядків описують кондиціонери. \(i\)-й з цих рядків містить \(a_i\), \(b_i\), \(p_i\), \(m_i\).

Для всіх тестів, крім тих, що у прикладі, можете вважати, що \(M = 10\).

Формат вихідних даних

Виведіть одне ціле число - мінімальну кількість грошей, яку ФД має витратити щоб зробити комфортною температуру для всіх корів.

Приклад вхідних даних

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

Одне можливе рішення - охолоджувати інтервали \([2, 9]\), \([1, 2]\), \([6, 9]\), із загальними витратами \(3 + 2 + 5 = 10 \).