Trang trại của ông Tuấn có một đàn bò \(n\) con thuộc \(k\) giống bò được nhốt mỗi con một chuồng trong dãy gồm \(m\) chuồng (\(m \ge n\)). Các giống bò được đánh số từ \(1\) đến \(k\). Các chuồng bò được đánh số thứ tự từ \(1\) đến \(m\) từ trái qua phải. Ông Tuấn muốn sắp xếp lại việc nhốt bò vào chuồng đáp ứng hai điều kiện sau đây:

1. Dễ bảo vệ: Đàn bò được nhốt trong \(n\) chuồng đầu tiên, mỗi chuồng một con.
2. Dễ chăm sóc: Các con bò cùng giống phải được nhốt trong các chuồng liên tiếp nhau.

Để thực hiện yêu cầu này, ông Tuấn có thể phải đổi chuồng nhốt cho một số con bò. Việc này có ảnh hưởng đến sức khỏe của bò. Giả sử bò thuộc giống bò thứ \(j\) có hệ số suy giảm sức khỏe \(h_j\) (\(j = 1, 2, \dots, k\)). Khi di chuyển một con bò thuộc giống \(j\) từ chuồng thứ \(p\) sang chuồng thứ \(q\) thì giá trị giảm sút sức khỏe của nó được tính theo công thức \(|p - q| \cdot h_j\).

Yêu cầu: Hãy giúp ông Tuấn sắp xếp lại chuồng nhốt cho đàn bò đáp ứng các điều kiện của ông Tuấn sao cho tổng giá trị giảm sút sức khỏe của cả đàn bò là nhỏ nhất.

Input

• Dòng thứ nhất chứa ba số nguyên dương \(m, n, k\) (\(n \le 10^5, m \le 10^6, 1 \le k \le 20\)).
• Dòng thứ hai chứa \(k\) số nguyên dương \(h_1, h_2, \dots, h_k\), trong đó \(h_j\) (\(h_j \le 10^5, 1 \le j \le k\)) là hệ số suy giảm sức khỏe của giống bò thứ \(j\).
• Mỗi dòng trong số \(n\) dòng tiếp theo chứa \(2\) số nguyên dương \(c, g\) cho biết chuồng thứ \(c\) đang nhốt con bò thuộc giống \(g\) (\(1 \le c \le m, 1 \le g \le k\)).

Output

• Ghi ra một số nguyên duy nhất là tổng giá trị giảm sút sức khỏe của cả đàn bò theo cách sắp xếp tìm được.

Example

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

40

Nguồn: Bài tập thầy Đỗ Đức Đông năm 2019