Với mùa hè nóng nhất từng được ghi nhận tại nông trại của Nông dân John, ông cần một cách để làm mát cho các con bò của mình. Do đó, ông quyết định đầu tư vào một số máy điều hòa.

Có \(N\) con bò của Nông dân John (\(1 \leq N \leq 20\)) sống trong một dãy chuồng, được đánh số từ \(1\) đến \(100\). Con bò thứ \(i\) chiếm một phạm vi chuồng, bắt đầu từ chuồng \(s_i\) và kết thúc tại chuồng \(t_i\). Các phạm vi của các con bò khác nhau đều không chồng lấn lên nhau. Các con bò có yêu cầu làm mát khác nhau. Con bò thứ \(i\) cần được làm mát bởi số lượng \(c_i\), có nghĩa là mỗi chuồng mà con bò \(i\) chiếm phải giảm nhiệt độ ít nhất là \(c_i\) đơn vị.

Trong chuồng có \(M\) máy điều hòa, được đánh số từ \(1\) đến \(M\) (\(1 \leq M \leq 10\)). Máy điều hòa thứ \(i\) tốn \(m_i\) đơn vị tiền để hoạt động (\(1 \leq m_i \leq 1000\)) và làm mát phạm vi chuồng từ chuồng \(a_i\) đến chuồng \(b_i\). Nếu hoạt động, máy điều hòa thứ \(i\) giảm nhiệt độ của tất cả các chuồng trong phạm vi này đi \(p_i\) đơn vị (\(1 \leq p_i \leq 10^6\)). Các phạm vi chuồng của các máy điều hòa có thể chồng lấn lên nhau.

Hãy tính số tiền tối thiểu mà Nông dân John cần phải chi để vận hành đủ máy điều hòa để làm mát tất cả các con bò của mình. Đảm bảo rằng nếu Nông dân John sử dụng tất cả các máy điều hòa của mình, thì tất cả các con bò sẽ thoải mái.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• \(N\) dòng tiếp theo mô tả thông tin về các con bò. Dòng thứ \(i\) chứa ba số nguyên \(s_i\), \(t_i\), và \(c_i\).
• \(M\) dòng tiếp theo mô tả thông tin về các máy điều hòa. Dòng thứ \(i\) chứa bốn số nguyên \(a_i\), \(b_i\), \(p_i\), và \(m_i\).
• Đối với các test khác test mẫu, bạn có thể giả định rằng \(M = 10\).

Output

• In ra một số nguyên duy nhất là số tiền tối thiểu mà Nông dân John cần phải chi để vận hành đủ máy điều hòa để làm mát tất cả các con bò.

Scoring

• Subtask 1: \(N \leq 5\).
• Subtask 2: \(N \leq 10\).
• Subtask 3: Không có ràng buộc gì thêm.

Example

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