Có ~M~ nhiệm vụ. Nhiệm vụ thứ ~i~ có:

• thời gian thực hiện ~x_i~
• độ khó ~y_i~

Nếu hoàn thành nhiệm vụ này, ta nhận được tiền thưởng:

~500 \times x_i + 2 \times y_i~

Có ~N~ máy. Máy thứ ~j~ có khả năng:

• làm việc tối đa trong ~T_j~ đơn vị thời gian
• xử lí nhiệm vụ có độ khó không vượt quá ~D_j~

Một máy có thể thực hiện nhiệm vụ ~i~ nếu:

• ~x_i \le T_j~
• ~y_i \le D_j~

Quy tắc

• Mỗi máy chỉ được làm nhiều nhất một nhiệm vụ.
• Mỗi nhiệm vụ chỉ được giao cho nhiều nhất một máy.

Yêu cầu

Hãy phân công nhiệm vụ cho các máy sao cho tổng tiền thưởng thu được là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên ~M, N~.
• Dòng thứ hai chứa ~2M~ số nguyên: ~x_1, y_1, x_2, y_2, \ldots, x_M, y_M~.
• Dòng thứ ba chứa ~2N~ số nguyên: ~T_1, D_1, T_2, D_2, \ldots, T_N, D_N~.

Output

In ra một số nguyên duy nhất là tổng tiền thưởng lớn nhất có thể đạt được.

Ràng buộc

• ~1 \le M, N \le 10^5~
• ~1 \le x_i \le 1440~
• ~1 \le y_i \le 200~
• ~1 \le T_j \le 1440~
• ~1 \le D_j \le 200~

Subtasks

• Subtask 1 (40%): ~M, N \le 20~
• Subtask 2 (30%): ~M, N \le 100~
• Subtask 3 (30%): Không có ràng buộc bổ sung.

Input

3 3
60 50 90 120 30 80
60 100 90 130 30 90

Output

90500