Алиса и Боб играют в игру в магазине. В магазине есть \(n\) предметов; каждый предмет имеет два параметра: \(a_i\) (цена предмета для Алисы) и \(b_i\) (цена предмета для Боба).
Алиса хочет выбрать подмножество (возможно, пустое) предметов и купить их. После этого Боб делает следующее:
- если Алиса купила меньше \(k\) предметов, Боб может взять их все бесплатно;
- в противном случае, он возьмет \(k\) предметов, купленные Алисой, бесплатно (Боб сам выбирает, какие \(k\) предметов это будут), а остальные выбранные предметы Боб купит у Алисы и заплатит \(b_i\) за \(i\)-й предмет.
Прибыль Алисы равна \(\sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j\), где \(S\) — множество предметов, которые Боб покупает у нее, а \(T\) — множество предметов, которые она покупает в магазине. Другими словами, прибыль Алисы — это разность между тем, сколько Боб платит ей, и тем, сколько она платит за покупку предметов.
Алиса хочет максимизировать свою прибыль, Боб хочет минимизировать прибыль Алисы. Ваша задача — посчитать прибыль Алисы, если и Алиса, и Боб действуют оптимально.
Выходные данные
Для каждого набора входных данных выведите одно целое число — прибыль Алисы, если и Алиса, и Боб действуют оптимально.
Примечание
В первом наборе входных данных Алисе следует купить \(2\)-й предмет и продать его Бобу, тогда ее прибыль составит \(2 - 1 = 1\).
Во втором наборе входных данных Алисе следует купить предметы \(1\), \(2\) и \(3\); затем Боб берет \(1\)-й предмет бесплатно и платит за \(2\)-й и \(3\)-й предметы. Прибыль Алисы составит \((3+2) - (1+2+1) = 1\). Боб мог бы взять \(2\)-й предмет бесплатно; это не изменит прибыль Алисы. Боб не будет брать \(3\)-й предмет бесплатно, так как тогда прибыль Алисы будет равна \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 0
2 1
1 2
4 1
1 2 1 4
3 3 2 3
4 2
2 1 1 1
4 2 3 2
6 2
1 3 4 9 1 3
7 6 8 10 6 8
|
1
1
0
7
|