Vận chuyển mèo

Có một con đường thẳng với $n$ ngọn đồi được đánh số $1,2,\dots ,n$ từ trái sang phải. Khoảng cách giữa đồi $i$ và đồi $i-1$ là $d_i$ mét (với $2\le i\le n$). Trên trang trại có $m$ con mèo và $p$ người nuôi mèo. Tất cả người nuôi đều sống tại đồi $1$.

Một ngày nọ, các con mèo đi chơi. Con mèo thứ $i$ đến đồi $h_i$, kết thúc chuyến đi tại thời điểm $t_i$, rồi đứng tại đồi $h_i$ chờ một người nuôi đến đón.

Mỗi người nuôi xuất phát từ đồi $1$, đi thẳng đến đồi $n$ với vận tốc $1$ mét/đơn vị thời gian, không dừng lại ở bất kỳ đồi nào. Khi đi qua một đồi, người nuôi đón tất cả các con mèo đang đợi sẵn ở đồi đó. Người nuôi có thể mang bao nhiêu mèo cũng được, và phải đón hết toàn bộ $m$ con mèo.

Người nuôi xuất phát từ đồi $1$ tại một thời điểm tự chọn. Nếu một người nuôi xuất phát tại thời điểm $s$, thì khi đến đồi $j$ thời điểm là $s+(d_2+d_3+\dots +d_j)$. Người này chỉ đón được mèo $i$ ở đồi $h_i$ nếu thời điểm tới đồi đó $\ge t_i$.

Thời gian chờ của một con mèo bằng thời điểm nó được đón trừ đi $t_i$. Hãy chọn thời điểm xuất phát cho từng người nuôi sao cho tổng thời gian chờ của tất cả $m$ con mèo là nhỏ nhất.

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$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $h_i$ và $t_i$ — đồi mèo $i$ tới và thời điểm nó hoàn thành chuyến đi.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng thời gian chờ tối thiểu 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$ với mọi $2\le i\le n$
• $1\le h_i\le n$ và $0\le t_i\le {10}^9$ với mọi $1\le i\le m$

Ví dụ