Air Cownditioning II

Nông dân John có $N$ con bò trong chuồng với các ô chuồng đánh số từ $1$ đến $100$. Con bò thứ $i$ chiếm các ô từ $s_i$ đến $t_i$ và cần được làm mát ít nhất $c_i$ đơn vị. Trang trại có $M$ máy điều hòa. Máy thứ $i$ làm mát các ô từ $a_i$ đến $b_i$ với công suất $p_i$ và chi phí $m_i$.

Hãy tìm chi phí tối thiểu để chạy đủ máy điều hòa sao cho tất cả các con bò đều đạt yêu cầu làm mát.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $M$
• $N$ dòng tiếp theo: mỗi dòng chứa $s_i$, $t_i$, $c_i$
• $M$ dòng tiếp theo: mỗi dòng chứa $a_i$, $b_i$, $p_i$, $m_i$

Dữ liệu ra

Một số nguyên duy nhất là chi phí tối thiểu.

Ràng buộc

• $1\le N\le 20$, $1\le M\le 10$
• $1\le m_i\le 1000$, $1\le p_i\le {10}^6$
• Các phạm vi ô chuồng của bò không giao nhau
• Sử dụng tất cả máy điều hòa luôn đảm bảo tất cả bò thoải mái

Ví dụ