Giáo sư K dùng \(N\) lá bài để bói kết quả của đoàn Nhật Bản tại IOI. Hai mặt của lá bài thứ \(i\) lần lượt ghi các số nguyên \(A_i\) và \(B_i\); hai số này không nhất thiết bằng nhau.

Ban đầu, tất cả lá bài được đặt sao cho mặt ghi \(A_i\) hướng lên. Sau đó, với mỗi \(j=1,2,\ldots,K\), giáo sư thực hiện thao tác sau: lật mọi lá bài có số đang hiện không lớn hơn \(T_j\).

Kết quả bói toán là tổng các số hiện trên bàn sau khi hoàn thành cả \(K\) thao tác. Hãy tính kết quả đó.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên \(N,K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(A_i,B_i\).
• \(K\) dòng tiếp theo, dòng thứ \(j\) chứa \(T_j\).

Dữ liệu ra

In ra tổng các số hiện trên các lá bài sau khi hoàn thành mọi thao tác.

Ràng buộc

• \(1 \le N,K \le 200\,000\).
• \(1 \le A_i,B_i \le 1\,000\,000\,000\).
• \(1 \le T_j \le 1\,000\,000\,000\).

Phân nhóm

• Nhóm 1 (4 điểm): \(N,K \le 1\,000\)
• Nhóm 2 (31 điểm): \(N,K \le 40\,000\)
• Nhóm 3 (65 điểm): Không có ràng buộc bổ sung

Ví dụ

5 3
4 6
9 1
8 8
4 2
3 7
8
2
9

18