Лиса Ciel играет в карты со своим другом Jiro.
У Jiro есть n карт, у каждой карты есть два атрибута: позиция position (атака или защита) и сила strength. У лисы Ciel есть m карт, аналогично, у каждой карты есть два атрибута. Известно, что позиция всех карт Ciel — это атака.
Пришло время Ciel атаковать! Она может выполнить следующую операцию много раз:
- Выбрать одну из своих карт X, которая не была выбрана ранее.
- Если у Jiro нет живых карт, он получит урон, равный (силе X). В противном случае, Ciel надо выбрать у Jiro одну живую карту Y, тогда:
- Если позиция Y — атака, то должно выполняться условие (сила X) ≥ (сила Y). После этой атаки карта Y умрет и Jiro получит урон, равный (сила X) - (сила Y).
- Если позиция Y — защита, то должно выполняться условие (сила X) > (сила Y). После этой атаки карта Y умрет, но Jiro не получит повреждений.
Ciel может в любой момент закончить атаковать Jiro (то есть она не обязана использовать все свои карты). Помогите Ciel посчитать максимальную сумму урона, которую можно нанести Jiro.
Выходные данные
Выведите целое число: максимальный ущерб, который можно нанести Jiro.
Примечание
В первом тесте все карты Ciel имеют одинаковую силу. Оптимальнее всего сначала напасть на карту «ATK 2000», уничтожить эту карту, тогда Jiro получит 2500 - 2000 = 500 единиц урона. Затем используем вторую карту для уничтожения карты «DEF 1700». Jiro не получает урона. Теперь у Jiro нет карт и можно использовать третью карту — нападаем на Jiro, он получает 2500 урона. Таким образом, ответ равняется 500 + 2500 = 3000.
Во втором тесте нужно использовать карту «1001» для атаки на карту «ATK 100», затем с помощью карты «101» напасть на карту «ATK 10». После этого у Ciel еще есть карты, но она может закончить атаковать. Таким образом, общий урон равен (1001 - 100) + (101 - 10) = 992.
В третьем случае заметьте, что Ciel может уничтожить карту «ATK 0» картой с силой, равной 0. Но не может уничтожить карту «DEF 0» картой с силой, равной 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
ATK 2000
DEF 1700
2500
2500
2500
|
3000
|
|
2
|
3 4
ATK 10
ATK 100
ATK 1000
1
11
101
1001
|
992
|
|
3
|
2 4
DEF 0
ATK 0
0
0
1
1
|
1
|