Vận chuyển mèo

Zxr960115 sở hữu một trang trại lớn. Anh ta nuôi $m$ con mèo dễ thương và thuê $p$ người cho ăn. Có một con đường thẳng chạy qua trang trại và $n$ ngọn đồi nằm dọc theo con đường, đánh số từ $1$ đến $n$ từ trái sang phải. Khoảng cách giữa đồi $i$ và đồi $i-1$ là $d_i$ mét. Những người cho ăn sống ở đồi $1$.

Một hôm, các con mèo đi chơi. Con mèo thứ $i$ đi tới đồi $h_i$, kết thúc chuyến đi tại thời điểm $t_i$, sau đó chờ tại đồi $h_i$ để có người đưa về.

Những người cho ăn phải đưa tất cả các con mèo về. Mỗi người đi thẳng từ đồi $1$ đến đồi $n$ không dừng lại ở đồi nào, và trên đường đi sẽ đón tất cả các con mèo đang chờ tại mỗi đồi. Người cho ăn di chuyển với tốc độ $1$ mét trên một đơn vị thời gian và có thể đón bao nhiêu mèo cũng được.

Nếu một người cho ăn rời đồi $1$ tại thời điểm $T$, thì tới đồi $h$ tại thời điểm $T+D_h$ (với $D_h$ là tổng khoảng cách từ đồi $1$ đến đồi $h$). Người này chỉ đón được các con mèo tại đồi $h$ đã hoàn thành chuyến đi tại thời điểm không muộn hơn $T+D_h$. Thời gian chờ của con mèo đó là $T+D_h-t$.

Nhiệm vụ của bạn là lên lịch thời điểm rời đồi $1$ cho mỗi người cho ăn (thời điểm phải là số nguyên không âm, có thể trùng nhau) sao cho tổng thời gian chờ của tất cả các con mèo là nhỏ nhất. Mọi con mèo đều phải được đưa về.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $p$.
• Dòng thứ hai chứa $n-1$ số nguyên dương $d_2,d_3,\dots ,d_n$.
• Trong $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $h_i$ và $t_i$.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng thời gian chờ nhỏ nhất của tất cả các con mèo.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le m\le {10}^5$
• $1\le p\le 100$
• $1\le d_i<{10}^4$
• $1\le h_i\le n$
• $0\le t_i\le {10}^9$

Ví dụ