У Косии есть \(n\) маркерных досок, пронумерованных от \(1\) до \(n\). Изначально на \(i\)-й доске написано целое число \(a_i\).
Косия выполнит \(m\) операций. На \(j\)-й операции она выберет одну из досок и заменит число, написанное на этой доске, на \(b_j\).
Найдите максимально возможную сумму чисел на досках после выполнения всех \(m\) операций.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную сумму чисел на досках после выполнения всех \(m\) операций.
Примечание
В первом примере Косия может выполнить операции следующим образом.
- Выбрать \(1\)-ю доску и заменить число на ней на \(b_1=4\).
- Выбрать \(2\)-ю доску и заменить число на \(b_2=5\).
После выполнения всех операций на досках будут написаны числа \(4\), \(5\) и \(3\) соответственно, их сумма равна \(12\). Можно показать, что это максимально возможная сумма.
Во втором примере Косия может выполнить операции следующим образом.
- Выбрать \(2\)-ю доску и заменить число на \(b_1=3\).
- Выбрать \(1\)-ю доску и заменить число на \(b_2=4\).
- Выбрать \(2\)-ю доску и заменить число на \(b_3=5\).
Сумма этих чисел равна \(4 + 5 = 9\). Можно показать, что это максимально возможная сумма.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 2
1 2 3
4 5
2 3
1 2
3 4 5
1 1
100
1
5 3
1 1 1 1 1
1000000000 1000000000 1000000000
|
12
9
1
3000000002
|