Игорь узнал о скидках в магазине и решил купить n товаров. Скидки в магазине продлятся неделю и Игорь знает про каждый товар, что сейчас он стоит ai, а после недели скидок будет стоить bi.
Не все из продавцов в магазине честные, поэтому некоторые товары сейчас стоят дороже, чем будут стоить после недели скидок.
Игорь решил, что купит не менее k товаров сейчас, а с остальными подождет неделю, чтобы максимально сэкономить. Перед вами стоит задача определить минимальную сумму, которую Игорь может потратить, чтобы купить все n товаров.
Выходные данные
Выведите минимальную сумму, которую Игорь может потратить, чтобы купить все n товаров при условии, что прямо сейчас он хочет купить не менее k товаров.
Примечание
В первом примере Игорю выгоднее всего купить сразу товар номер 3, заплатив за это 6, а товары номер 1 и 2 подождать, тогда он сможет купить их за 3 и 1, соответственно. Суммарно Игорь заплатит 6 + 3 + 1 = 10.
Во втором примере Игорю выгоднее всего купить сразу товары с номерами 1, 2, 4 и 5, заплатив за них 3, 4, 10 и 3, соответственно. Товар номер 3 Игорю выгоднее купить после скидок, он заплатит за это 5. Суммарно Игорь заплатит 3 + 4 + 10 + 3 + 5 = 25.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
5 4 6
3 1 5
|
10
|
|
2
|
5 3
3 4 7 10 3
4 5 5 12 5
|
25
|