Có \(n\) loại hình hộp chữ nhật và \(m\) loại hình trụ tròn, loại hình hộp chữ nhật thứ \(i\) có kích thước \( x_i, y_i, z_i\) , loại hình trụ tròn thứ \(j\) có bán kính đáy là \(r_j\) và chiều cao là \(h_j\) . Tiến hành xếp chồng các hình hộp chữ nhật và hình trụ theo nguyên tắc:

• Mỗi loại hình được sử dụng nhiều lần;

• Các hình hộp chữ nhật được đặt sao cho các cạnh song song với hệ trục tọa độ;

• Mỗi hình đặt lên tạo thành một lớp. Mỗi lớp chỉ có đúng một hình. Hình nằm trên đặt gọn trong hình nằm dưới.

Yêu cầu:

• Tìm cách xếp để nhận được chồng các hình cao nhất.

Input

• Dòng 1: chứa hai số \(n, m\) ;

• Dòng 2 đến dòng \(n+1\), mỗi dòng chứa 3 số nguyên \(x_i, y_i, z_i\) mô tả \(n\) hình hộp chữ nhật;

• Dòng \(n+2\) đến dòng \(n+m+1\), mỗi dòng chứa 2 số nguyên \(r_j, h_j\) mô tả \(m\) hình trụ tròn. \((0<x_i, y_i, z_i, r+j, h_j ≤10^9) \)

Output

• Gồm một dòng là độ cao lớn nhất tìm được.

Ràng buộc

• Subtask 1: 20% test \(n=0, m ≤ 100\)

• Subtask 2: 20% test \(n ≤ 100, m=0\)

• Subtask 3: 60% test \(n ≤ 100, m ≤ 100\)

Sample Input

1 0 
10 20 30

Sample Output

40

Giới hạn