THỰC HÀNH

Nhân dịp chào xuân Kỷ Hợi 2019, Thành phố Sơn La đã tổ chức bắn N loạt pháo hoa vào các thời điểm phân biệt (tính từ lúc giao thừa). Loạt thứ i bắn n_i quả vào thời điểm t_i. Trong không khí nô nức đi xem pháo hoa, người ta thống kê được có M người đến xem, người thứ i đến vào thời điểm d_i và ra về vào thời điểm v_i.

Yêu cầu: Tính số lượng pháo hoa mà mỗi người đến xem đã quan sát được (loạt pháo hoa được bắn vào thời điểm một người đến xem hay ra về cũng được tính là người đó quan sát được).

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương N và M.
• N dòng tiếp theo, dòng thứ i chứa hai số nguyên n_i và t_i là số lượng pháo hoa và thời điểm bắn của loạt thứ i.
• M dòng tiếp theo, dòng thứ i chứa hai số nguyên d_i và v_i­ là thời điểm đến và về của người thứ i.

Dữ liệu ra:

Ghi ra trên một dòng n số nguyên, số thứ i là số lượng pháo hoa người thứ i đã quan sát được.

Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:
3 2
3 1
2 4
1 2
1 3
2 5

Dữ liệu ra:
4 3

Giải thích:

Người thứ nhất xem được hai loạt bắn vào thời điểm 1 (3 quả) và thời điểm 2 (1 quả). Tổng là 4 quả.

Người thứ hai xem được hai loạt bắn vào thời điểm 2 (1 quả) và thời điểm 4 (2 quả). Tổng là 3 quả.

Giới hạn:

Trong tất cả các bộ dữ liệu (test) có 1 ≤ N, M ≤ 10⁵; 1 ≤ n_i ≤ 100; 0 ≤ t_i ≤ 10⁹; 0 ≤ d_i ≤ v_i ≤ 10⁹.

• Subtask #1: 60% số test ứng với 60% số điểm có N, M ≤ 10³; 0 ≤ t_i, d_i, v_i ≤ 10⁴.
• Subtask #2: 30% số test khác ứng với 30% số điểm có N, M ≤ 10⁵; 0 ≤ t_i, d_i, v_i ≤ 10⁶.
• Subtask #3: 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.