D. Муур тээвэрлэлт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Zxr960115 бол том фермерийн эзэн. Тэр $m$ тооны хөөрхөн муур тэжээдэг ба $p$ тооны ажилчид ажиллуулдаг. Фермийн нөгөө талд шулуун зам байгаа ба замын дагуу $1$-ээс $n$ хүртэл дугаарлагдсан $n$ толгод байна. $i$-р толгод болон $(i-1)$-р толгодын хоорондох зай нь $d_{i}$ метр байна. Ажилчид 1-р толгодод амьдардаг.

Нэг өдөр муурнууд тоглохоор гарсан. $i$-р муур $h_{i}$ толгодруу явсан ба $t_{i}$ цагт очсон ба ажилчныг $h_{i}$ толгод дээр хүлээсэн. Ажилчид бүх муурыг авах ёстой. Ажилчин бүр 1-р толгодоос $n$-р толгод хүртэл явах ба толгод дээр хүлээхгүй ба толгод бүр дээр хүлээж буй бүх муурнуудыг авна. Ажилчид нэгж хугацаанд 1 метр алхах ба ажилчид хэдэн ч муур өргөж дийлэхээр хүчтэй гэж үз.

Жишээлбэл, бидэнд 2 толгод байна $(d_{2}=1)$ мөн нэг муур байгаа бөгөөд муур толгод 2 буюу $(h_{1}=2)$ дээр хугацааны 3-р агшинд ирсэн. Хэрвээ ажилчин толгод 1-ээс хугацааны 2-р агшинд эсвэл 3-р агшинд гарсан бол муурыг авч чадна, гэхдээ ажилчин 1-р толгодоос хугацааны 1-р агшинд гарсан бол муурыг авч чадахгүй. Ажилчин толгод 1-ээс хугацааны 2-р агшинд гарсан бол муур түүнийг 0 хугацааны агшинд хүлээх ба хэрвээ ажилчин толгод 1-ээс хугацааны 3-р агшинд гарсан бол муур түүнийг 1 хугацааны агшинд хүлээнэ.

Таны ажил бол ажилчин бүрийн толгод 1-ээс гарсан цагийг хуваарилах ба муур бүрийн хүлээх байж болох хамгийн бага цагуудын нийлбэрийг олох юм.

Оролт

Эхний мөрөнд гурван ширхэг бүхэл тоон утга байх ба эдгээр нь $n, m, p$ $(2 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 10^{5}, 1 ≤ p ≤ 100)$. The first line of the input contains three integers $n, m, p$ $(2 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 10^{5}, 1 ≤ p ≤ 100)$.

Хоёр дахь мөрөнд $n-1$ эерэг бүхэл тоо байх ба эдгээр нь $d_{2}, d_{3}, ..., d_{n}$ $(1 ≤ d_{i} < 10^{4})$. The second line contains $n - 1$ positive integers $d_{2}, d_{3}, ..., d_{n}$ $(1 ≤ d_{i} < 10^{4})$.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоо байх ба $h_{i}$ ба $t_{i}$ $(1 ≤ h_{i} ≤ n, 0 ≤ t_{i} ≤ 10^{9})$ юм. Each of the next $m$ lines contains two integers $h_{i}$ and $t_{i}$ $(1 ≤ h_{i} ≤ n, 0 ≤ t_{i} ≤ 10^{9})$.

Гаралт

Бүх муурны хүлээх хугацааны байж болох хамгийн бага нийлбэрийг хэвлэнэ. Output an integer, the minimum sum of waiting time of all cats.

C++ хэл дээр 64 битийн бүхэл тоог унших болон бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. Харин $cin$, $cout$ урсгалууд эсвэл $\%I64d$ тодорхойлогчийг ашиглаарай.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...