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 >= 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, …, 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| × 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.

Dữ liệu:

- Dòng thứ nhất chứa ba số nguyên dương m, n, k ( n ≤ 10⁵ , m ≤ 10⁶ , 1 ≤ k ≤ 20);
- Dòng thứ hai chứa k số nguyên dương h₁ , h₂ , …, h_k , trong đó h_j (h_j ≤ 10⁵ , 1 ≤ j ≤ 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≤ c ≤ m, 1 ≤ g ≤ k).

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

Kết quả:

Ghi ra một số nguyên 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.