Lan muốn đi tập gym. Cậu có thể chọn một số ngày trong $1 \sim n$ ngày sắp tới để đi tập.

Cậu có $m$ kế hoạch tập luyện. Kế hoạch thứ $i$ cần $2^{k_i}$ ngày liên tiếp; nếu hoàn thành trọn vẹn sẽ nhận được lợi ích tập luyện $s_i$ , nếu bị gián đoạn thì không nhận được gì.

Cùng một kế hoạch tập luyện có thể hoàn thành nhiều lần và nhận lợi ích tập luyện nhiều lần, nhưng trong cùng một ngày không thể thực hiện đồng thời từ hai kế hoạch tập luyện trở lên.

Tuy nhiên trong lịch của cậu có $q$ ngày đã có việc bận khác, không thể đi tập. Hỏi nên sắp xếp các kế hoạch tập luyện thế nào để tổng lợi ích tập luyện trong $n$ ngày là lớn nhất.

Dữ liệu vào

Dòng đầu tiên nhập ba số nguyên $n, m, q$ .

Dòng thứ hai nhập $q$ số nguyên $t_1, t_2, t_3, \dots, t_q$ , là những ngày đã có việc bận khác.

$m$ dòng tiếp theo, mỗi dòng nhập hai số nguyên $k_i, s_i$ , nghĩa là kế hoạch tập luyện đó cần $2^{k_i}$ ngày, hoàn thành xong sẽ nhận được lợi ích tập luyện $s_i$ .

Dữ liệu ra

Một số nguyên, là tổng lợi ích tập luyện lớn nhất.

Ví dụ

Input

10 3 3
1 4 9
0 3
1 7
2 20

Output

30

Ghi chú

Giải thích mẫu

Trong ví dụ, các ngày $2 \sim 3$ thực hiện kế hoạch 2, các ngày $5 \sim 8$ thực hiện kế hoạch 3, ngày $10 \sim 10$ thực hiện kế hoạch 1.

Phạm vi dữ liệu

• $1 \leq q \leq n \leq 2 \times 10^5$

• $1 \leq m \leq 50$

• $1 \leq s_i \leq 10^9$

• $0 \leq k_i \leq 20$

• $1 \leq t_1 < t_2 < \dots < t_q \leq n$