ZXR960115 містить велике господарство. Він годує \(m\) милих кішечок і тримає у себе \(р\) годувальників. Через ферму проходить пряма дорога, а вздовж дороги розташовано \(n\) пагорбів, пронумерованих від 1 до \(n\), зліва направо. Відстань від пагорба \(i\) до \(i - 1\) дорівнює \(d_i\) метрів. Годувальники мешкають на пагорбі 1.

Одного разу кішечкам захотілося повеселитись і вони розбіглися. Кішка \(i\) пішла до пагорба \(h_i\), дійшла до нього в момент часу \(t_i\), а потім почала чекати годувальника на пагорбі \(h_i\). Годувальники повинні зібрати всіх котів, що розбіглися. Кожен годувальник йде прямо від пагорба номер 1 до пагорба номер \(n\), не зупиняючись біля будь-якого пагорба, і збирає всіх кішок, які чекають на кожному пагорбі. Годувальники рухаються зі швидкістю 1 в одиницю часу і досить сильні, щоб зібрати скільки завгодно кішок.

Наприклад, нехай є два пагорби (\(d_2=1\)) і одна кішечка, яка дійшла до пагорба 2 (\(h_1=2\)) в момент часу 3. Тоді, якщо годувальник відправиться за кішками від пагорба 1 в момент часу 2 або 3, то він зможе забрати цю кішку. Але якщо він вирушить від пагорба 1 в момент часу 1, то він не зможе цього зробити. Якщо годувальник відправиться за кішкою в момент часу 2, то кішка чекатиме його 0 одиниць часу, якщо ж він вирушить у момент часу 3, то кішка чекатиме на його 1 одиницю часу.

Ваше завдання - скласти розклад відправки від пагорба 1 для годувальників так, щоб загальний час очікування кішок до того, як їх заберуть, був мінімальним.

Формат вхідних даних

У першому рядку вхідних даних міститься три цілих числа \(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\)).

У кожному з наступних \(m\) рядків міститься по два цілих числа \(h_i\) і \(t_i\) (\(1 ≤ h_i ≤ n\), \(0 ≤ t_i ≤ 10^9\)).

Формат вихідних даних

Виведіть ціле число, мінімальну суму часів очікування всіх кішок.

Будь ласка, не використовуйте специфікатор %lld для читання та запису 64-бітових чисел на C++. Рекомендується використовувати потоки cin, cout або специфікатор % I64d.

Приклад вхідних даних

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

Приклад вихідних даних

3