Степан кине монету \(N\) разів. У нього також є лічильник, який спочатку показує 0. Залежно від результату \(i\)-го підкидання монети відбувається:

• Якщо випав герб: Степан збільшує значення лічильника на 1 і отримує \(X_i\) грн.

• Якщо випала копійка: він скидає значення лічильника до 0, не отримуючи грошей.

Крім того, існують \(M\) видів бонусів. \(І\)-й вид серії бонусів присуджує \(Y_i\) грн кожного разу, коли лічильник показує \(C_i\).

Знайдіть максимальну суму грошей, яку може отримати Степан.

Обмеження

• \(1 \leq M \leq N \leq 5000\)
• \(1 \leq X_i \leq 10^9\)
• \(1 \leq C_i \leq N\)
• \(1 \leq Y_i \leq 10^9\)
• \(C_1,C_2,\ldots,C_M\) всі різні.
• Усі значення у вхідних даних є цілими числами.

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

Перший рядок містить цілі числа \(N,M\)

Наступний  рядок містить \(N\) цілих чисел \(X_i\)

Наступні  \(N\) рядків містять цілі числа \(C_i, Y_i\)

Числа у рядках розділяються пропуском.

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

У вихідний потік виведіть відповідь

Примітка

До прикладу 1:

Якщо він отримує герб, герб, копійку, герб, герб, герб, у такому порядку, то він заробить 48 грн.

У випадку коли він отримував кожного разу лише герб, то виграш становив би лише 44 грн.

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

6 3
2 7 1 8 2 8
2 10
3 1
5 5

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

48

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

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

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

5000000000