Ви маєте \(N\) карток. На \(i\)-й картці написано ціле число \(A_i\).

Для \(j = 1, 2, ..., M\) у цьому порядку ви виконаєте таку операцію один раз:

• Операція: Виберіть не більше \(B_j\)​ карток (можливо, нуль). Замініть ціле число, записане на кожній вибраній картці, на \(C_j\).

Знайдіть максимально можливу суму цілих чисел, записаних на \(N\) картках після \(M\) операцій.

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

Перший рядок вхідного потоку містить цілі числа \(N, M\) (\(1 \le N,M \le 10^5\))

Другий рядок містить \(N\) цілих чисел \(A_i\) (\(1 \le A_i \le 10^9\)).

Наступні \(M\) рядків містять пари цілих чисел \(B_i, C_i\) (\(1 \le B_i \le N\), \(1 \le C_i \le 10^9\))

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

У вихідний потік виведіть максимально можливу суму цілих чисел, записаних на \(N\) картках після \(M\) операцій.

Примітка

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

Замінивши ціле число на другій картці на 5, сума цілих чисел, записаних на трьох картках, стане 5 + 5 + 4 = 14, що є максимальним результатом.

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

3 2
5 1 4
2 3
1 5

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

14

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

10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4

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

338

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

3 2
100 100 100
3 99
3 99

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

300