Mùa đông đã đến, những bạn đang xem live của CLB lập trình Fullhouse thì đều đang rất cô đơn và lạnh lẽo vì không có người yêu. Vì là một người tốt nên giảng viên của câu lạc bộ đã có kế hoạch lắp máy sưởi cho các bạn FA.

Có \(N( N ≤ 20)\) người sống trong một dãy các căn phòng được đánh số từ \(1\) đến \(100\). Người thứ \(i\) sống trong căn phòng từ \(s_i\) đến \(t_i\). Mỗi người trái tim đều có độ lạnh lẽo khác nhau nên yêu cầu khả năng làm ấm khác nhau. Người thứ \(i\) cần được làm ấm một lượng \(c_i\) nghĩa là mỗi căn nhà mà người thứ \(i\) chiếm giữ cần được tăng nhiệt độ ít nhất \(c_i\) đơn vị. Fullhouse có \(M\) máy sưởi không khí, được đánh số từ \(1\) đến \(M (1≤M≤10 )\).

Máy sưởi thứ \(i\) có chi phí hoạt động là \(m_i\) đơn vị tiền \((1≤m_i≤1000 )\) và làm mát dãy nhà bắt đầu từ nhà \(a_i\) và kết thúc ở nhà \(b_i\). Nếu hoạt động, máy sưởi thứ \(i\) sẽ tăng nhiệt độ của tất cả các nhà trong dãy này lên \(p_i\) đơn vị \((1≤p_i≤10^6 )\). Các dãy nhà được máy điều hòa phủ sóng có thể chồng lên nhau.

Hãy xác định số tiền tối thiểu mà Fullhouse cần chi tiêu để giữ cho tất cả mọi người thoải mái.

INPUT FORMAT

Dòng đầu tiên của đầu vào chứa \(N\) và \(M\)

\(N\) dòng tiếp theo mô tả người. Dòng thứ \(i\) trong số này chứa \(s_i , t_i , và c_i\)

\(M\) dòng tiếp theo mô tả máy điều hòa. Dòng thứ \(i\) trong số này chứa \(a_i , b_i , p_i\) , và \(m_i\).

OUTPUT FORMAT

In ra một số nguyên duy nhất là đáp án.

Ví dụ:

Input

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

Output

10

Một giải pháp khả thi mang lại số tiền chi tiêu ít nhất là chọn những giải pháp làm ấm các khoảng [2,9], [1,2] và [6,9] , với chi phí là 3+2+5=10.

Giải thích ví dụ mẫu

• Ví dụ 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

  Giải thích: Để đáp ứng nhu cầu làm ấm của tất cả mọi người với chi phí tối thiểu, bạn cần chọn máy sưởi để bao phủ các khoảng [2,9], [1,2] và [6,9] với tổng chi phí là 10.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House