Hải có ~n~ quân domino xếp thành một hàng ngang, đánh số từ trái sang phải từ 1 đến ~n~. Một mặt của domino thứ ~i~ ghi số nguyên dương ~a_i~, mặt còn lại ghi số nguyên dương ~b_i~. Ban đầu, xếp các quân domino sao cho mặt ghi ~a_i~ quay lên trên, mặt ghi ~b_i~ quay xuống dưới.

Hải thực hiện thao tác sau ~k~ lần: Cho một số nguyên dương ~T~, lật tất cả những quân domino có số được ghi ở mặt trên nhỏ hơn hoặc bằng ~T~.

Yêu cầu: Sau khi thực hiện đủ ~k~ lần, hãy tính tổng ~n~ số được ghi trên mặt đang quay lên trên.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ (~1 \le n, k \le 2 \times 10^5~);
• ~n~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~a_i, b_i~ (~1 \le a_i, b_i \le 10^9~) là hai số được ghi trên quân domino thứ ~i~. Ban đầu, mặt ~a_i~ được quay lên trên, còn mặt ~b_i~ quay xuống dưới;
• ~k~ dòng sau, dòng thứ ~i~ gồm một số nguyên dương ~T_i~ (~1 \le T_i \le 10^9~) là giá trị được chọn cho thao tác thứ ~i~.

Output

• Ghi ra một số nguyên dương duy nhất là tổng ~n~ số được ghi trên mặt quay lên trên của ~n~ quân domino.