Đạt 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~ . Đạt 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, Đạt 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~ x ~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 Đạt 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 chiều cao ~h_i~ và chiều rộng ~w_i~ của quyển sách
• 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~ 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í phí ít nhất để dựng một số giá sách chứa tất cả các quyển sách.

Ví dụ:

Input

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

Output

1680

Ràng buộc:

• Có 25% số test ứng với: ~n~ <= 20; ~m~ <= 2;
• Có 25% số test ứng với : ~n~ <= 1000; ~m~ <= 10;
• Có 25% số test ứng với : ~n~ <= 100; ~m~ <= 100;
• Có 25% số tests ứng với : ~n~ <= 1000; ~m~ <= 1000;