Bờm có \(n\) quyển sách, quyển sách thứ \(i\) có chiều cao \(h_i\) và chiều rộng \(w_i\). Bờm muốn xây dựng một số giá sách để chứa hết tất cả \(n\) quyển sách này. Qua tìm hiểu, Bờm nhận được các thông tin sau: Nhà sản xuất nhận làm \(m\) loại giá sách, mỗi loại giá sách gồm các thông tin \(H_i, F_i, C_i\). Giá sách loại thứ \(i\) có thể chứa được các quyển sách có độ cao không vượt quá \(H_i\) và nếu muốn dựng giá sách có độ rộng là \(W\) thì giá tiền tương ứng là \(F_i + W \times C_i\).

Yêu cầu: Cho thông tin về các quyển sách và các loại giá sách, hãy giúp Bờm tính chi phí ít nhất để dựng một số giá sách chứa tất cả các quyển sách.

Input

• Dòng \(1\): gồm \(2\) số \(n, m\).
• Dòng \(2\) đến dòng \(n+1\): mỗi dòng chứa \(2\) số nguyên dương mô tả chiều cao \(h_i\) và chiều rộng \(w_i\) của quyển sách (\(h_i, w_i \leq 10^9\)).
• Dòng thứ \(n+2\) đến dòng \(n+m+1\): mỗi dòng chứa \(3\) số nguyên dương \(H_i, F_i, C_i\) (\(H_i, F_i, C_i \leq 10^9\)) mô tả các thông tin về các loại giá sách.

Output

• Gồm một dòng chứa một số là chi phí ít nhất để dựng một số giá sách chứa tất cả các quyển sách.

Example

3 3
20 5
21 10
22 5
20 100 1
21 150 2
25 1000 100

1680

Scoring

• Subtask \(1\): \(n \leq 20\); \(m \leq 2\) \([25\) tests\(]\)
• Subtask \(2\): \(n \leq 1000\); \(m \leq 10\) \([25\) tests\(]\)
• Subtask \(3\): \(n \leq 100\); \(m \leq 100\) \([25\) tests\(]\)
• Subtask \(4\): \(n \leq 1000\); \(m \leq 1000\) \([24\) tests\(]\)