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×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 (n, m<=1000)

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 (h_i,w_i≤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≤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í phí ít nhất để dựng một số giá sách chứa tất cả các quyển sách.

Sample Input

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

Sample Output

1680