На свой день рождения Петя пригласил \(n\) друзей, у \(i\)-го друга есть параметр \(k_i\). Каждому из приглашенных друзей Петя хочет подарить ровно один подарок. В магазине есть \(m\) различных подарков, которые Петя может купить, каждый подарок можно купить не более одного раза. Подарок номер \(j\) стоит \(c_j\) рублей (\(1 \le c_1 \le c_2 \le \ldots \le c_m\)).
Для \(i\)-го друга Петя может либо купить ему подарок \(j \le k_i\), что будет стоить Пете \(c_j\) рублей, либо заплатить другу \(c_{k_i}\) рублей вместо подарка. Помогите Пете определить наименьшую возможную стоимость проведения праздника.
Выходные данные
Для каждого набора входных данных выведите минимальное число рублей, которое понадобится Пете для приобретения всех подарков.
Примечание
В примере есть два набора входных данных. В первом у Пети есть \(5\) друзей и \(4\) возможных подарка. Ответ \(30\) достигается, если подарить:
- \(5\) рублей первому другу.
- подарок стоимости \(12\) рублей второму другу.
- подарок стоимости \(5\) рублей третьему другу.
- подарок стоимости \(3\) рубля четвертому другу.
- \(5\) рублей пятому другу.
Во втором у Пети есть \(5\) друзей и \(5\) возможных подарков. Ответ \(190\) достигается, если подарить:
- подарок стоимости \(10\) рублей первому другу.
- подарок стоимости \(40\) рублей второму другу.
- \(90\) рублей третьему другу.
- \(40\) рублей четвертому другу.
- \(10\) рублей пятому другу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 4
2 3 4 3 2
3 5 12 20
5 5
5 4 3 2 1
10 40 90 160 250
|
30
190
|
|
2
|
1
1 1
1
1
|
1
|