Codeforces Round 190 (Div. 1) |
---|
Закончено |
Лиса Ciel играет в карты со своим другом Jiro.
У Jiro есть n карт, у каждой карты есть два атрибута: позиция position (атака или защита) и сила strength. У лисы Ciel есть m карт, аналогично, у каждой карты есть два атрибута. Известно, что позиция всех карт Ciel — это атака.
Пришло время Ciel атаковать! Она может выполнить следующую операцию много раз:
Ciel может в любой момент закончить атаковать Jiro (то есть она не обязана использовать все свои карты). Помогите Ciel посчитать максимальную сумму урона, которую можно нанести Jiro.
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 100) — количество карт у Jiro и Ciel.
Каждая из следующих n строк содержит строку position и целое число strength (0 ≤ strength ≤ 8000) — позиция и сила текущей карты Jiro. Позиция position — это строка «ATK» для позиции атака, и строка «DEF» для позиции защита.
Каждая из следующих m строк содержит целое число strength (0 ≤ strength ≤ 8000) — сила текущей карты Ciel.
Выведите целое число: максимальный ущерб, который можно нанести Jiro.
2 3
ATK 2000
DEF 1700
2500
2500
2500
3000
3 4
ATK 10
ATK 100
ATK 1000
1
11
101
1001
992
2 4
DEF 0
ATK 0
0
0
1
1
1
В первом тесте все карты 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.
Название |
---|