Vận chuyển mèo

Quanlt206 là một người chủ trang trại có một đàn mèo cực kỳ đáng yêu! Anh ta nuôi \(m\) chú mèo và thuê \(p\) người cho ăn. Có một con đường thẳng chạy xuyên qua trang trại với \(n\) ngọn đồi nằm dọc theo con đường, đánh số từ 1 đến \(n\) từ trái qua phải. Khoảng cách giữa ngọn đồi \(i\) và \((i - 1)\) là \(d_i\) mét. Các người cho ăn đều sống tại ngọn đồi 1.

Vào một ngày đẹp trời, các chú mèo quyết định đi dạo chơi. Chú mèo \(i\) đi đến ngọn đồi \(h_i\), kết thúc chuyến đi vào thời điểm \(t_i\), và sau đó ngồi chờ ở đó để được một người cho ăn đón về. Các người cho ăn phải đón hết tất cả các chú mèo. Mỗi người cho ăn sẽ đi thẳng từ ngọn đồi 1 đến ngọn đồi \(n\) mà không dừng lại, và đón tất cả các chú mèo đang chờ đợi tại mỗi ngọn đồi mà họ đi qua. Tất cả người cho ăn đều di chuyển với tốc độ 1 mét mỗi đơn vị thời gian và có thể đón được bất kỳ số lượng mèo nào mà không gặp khó khăn.

Ví dụ minh họa: Giả sử có hai ngọn đồi \((d_2 = 1)\) và một chú mèo đã kết thúc chuyến đi tại thời điểm 3 ở ngọn đồi 2 \((h_1 = 2)\). Khi đó, nếu người cho ăn rời ngọn đồi 1 vào thời điểm 2 hoặc 3, anh ta có thể đón chú mèo này. Nhưng nếu người cho ăn rời ngọn đồi 1 tại thời điểm 1, chú mèo sẽ không được đón kịp. Nếu người cho ăn rời ngọn đồi 1 tại thời điểm 2, chú mèo phải chờ 0 đơn vị thời gian; nếu người cho ăn rời ngọn đồi 1 tại thời điểm 3, chú mèo phải chờ thêm 1 đơn vị thời gian.

Nhiệm vụ của bạn: Hãy lập kế hoạch cho từng người cho ăn xuất phát từ ngọn đồi 1 sao cho tổng thời gian chờ đợi của tất cả các chú mèo là nhỏ nhất.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(p\) \((2 \leq n \leq 10^5, 1 \leq m \leq 10^5, 1 \leq p \leq 100)\) --- số lượng ngọn đồi, số lượng mèo, và số lượng người cho ăn.
• Dòng thứ hai chứa \(n - 1\) số nguyên \(d_2, d_3, \ldots, d_n\) \((1 \leq d_i \leq 10^4)\) --- khoảng cách giữa các ngọn đồi liên tiếp.
• Mỗi dòng trong \(m\) dòng tiếp theo chứa hai số nguyên \(h_i\) và \(t_i\) \((1 \leq h_i \leq n, 0 \leq t_i \leq 10^9)\) --- vị trí ngọn đồi và thời điểm chú mèo \(i\) kết thúc chuyến đi.

Output

In ra một số nguyên duy nhất --- tổng thời gian chờ đợi nhỏ nhất có thể của tất cả các chú mèo.

Example

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

3

Scoring

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(p = 1\).

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(m \leq 10\).

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(m \leq 500, h_{i} = h_{i + 1}\).

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(m \leq 500\).

• \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.