原題來(lái)自：Codeforces Round #185 (Div. 1) B.

小 S 是農(nóng)場(chǎng)主，他養(yǎng)了 M 只貓，雇了 P 位飼養(yǎng)員。農(nóng)場(chǎng)中有一條筆直的路，路邊有 N 座山，從 1 到 N 編號(hào)。第 i 座山與第 i?1 座山之間的距離是 D_i 。飼養(yǎng)員都住在 1 號(hào)山上。

有一天，貓出去玩。第 i 只貓去 Hi號(hào)山玩，玩到時(shí)刻 Ti 停止，然后在原地等飼養(yǎng)員來(lái)接。飼養(yǎng)員們必須回收所有的貓。每個(gè)飼養(yǎng)員沿著路從 1 號(hào)山走到 N 號(hào)山，把各座山上已經(jīng)在等待的貓全部接走。飼養(yǎng)員在路上行走需要時(shí)間，速度為 1 米每單位時(shí)間。飼養(yǎng)員在每座山上接貓的時(shí)間可以忽略，可以攜帶的貓的數(shù)量為無(wú)窮大。

例如有兩座相距為 1 的山，一只貓?jiān)?2 號(hào)山玩，玩到時(shí)刻 3 開(kāi)始等待。如果飼養(yǎng)員從 1 號(hào)山在時(shí)刻 2 或 3 出發(fā)，那么他可以接到貓，貓的等待時(shí)間為 0 或 1。而如果他于時(shí)刻 1 出發(fā)，那么他將于時(shí)刻 2 經(jīng)過(guò) 2 號(hào)山，不能接到當(dāng)時(shí)仍在玩的貓。

你的任務(wù)是規(guī)劃每個(gè)飼養(yǎng)員從 1 號(hào)山出發(fā)的時(shí)間，使得所有貓等待時(shí)間的總和盡量小。飼養(yǎng)員出發(fā)的時(shí)間可以為負(fù)。

第一行三個(gè)整數(shù) N,M,P；

第二行 N?1 個(gè)正整數(shù) D_i ，表示第 i 座山與第 i?1 座山之間的距離是 D_i ；

接下去 M 行每行兩個(gè)整數(shù) H_i,T_i 。

數(shù)據(jù)范圍與提示：

對(duì)于全部數(shù)據(jù)，2≤N≤10⁵,1≤M≤10⁵,1≤p≤100,1≤D_i<10⁴,1≤H_i≤N,0≤T_i≤10⁹ 。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃