Bờm có n quyển sách, quyển sách thứ i có chiều cao hi và chiều rộng wi. 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: Hi,Fi,Ci. 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á Hi và nếu muốn dựng giá sách có độ rộng là W thì giá tiền tương ứng là: Fi+W×Ci.
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 chiều cao hi và chiều rộng wi của quyển sách (hi,wi≤109)
Dòng thứ n+2 đến dòng n+m+1, mỗi dòng chứa 3 số nguyên dương Hi,Fi,Ci. (Hi,Fi,Ci. ≤109) 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.
Input
3 3
20 5
21 10
22 5
20 100 1
21 150 2
25 1000 100
Output
1680
Giới hạn:
Subtask 1: n≤20;m≤2 [25 tests]
Subtask 2: n≤1000;m≤10 [25 tests]
Subtask 3: n≤100;m≤100 [25 tests]
Subtask 4: n≤1000;m≤1000 [24 tests]
Nguồn: 3D '1819