Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2117. Вор
Деревья (map, set), хэш-таблицыОлимпиадные задачи на русском языке
| 16/07/2014 | Лето 2014 - 12 (D) |
| 13/07/2020 | Летние сборы - 7 (E) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Сложная экономическая ситуация в стране и сокращение государственного финансирования
сельского хозяйства вызвали у Мирко желание снова изменить свою карьеру, на этот раз он стал вором.
Свои первые профессиональные усилия он направил на ювелирный магазин.
В магазине есть N ювелирных украшений, каждое из них имеет некоторую масса Mi и ценность Vi.
Мирко имеет K мешков для хранения награбленного, и каждый мешок может содержать
некоторую максимальную массу Ci.
Мирко планирует унести всю свою добычу в этих мешках, но не более одного ювелирного изделия в каждом мешке,
с тем чтобы уменьшить вероятность их повреждения во время побега.
Найти максимальную общую стоимость ювелирных изделий, которые Мирко может "освободить".
Первая строка входного файла содержит два целых числа N и K (1 ≤ N, K ≤ 300 000).
Каждая из следующих N строк содержит пару целых чисел Мi и Vi (1 ≤ Mi, Vi ≤ 1 000 000).
Каждая из следующих K строк содержит одно целое число Сi (1 ≤ Ci ≤ 100 000 000).
Первая и единственная строка вывода должна содержать максимально возможную суммарную стоимость драгоценностей.
Пример ввода 1
2 1 5 10 100 100 11
Пример вывода 1
10
Пример ввода 2
3 2 1 65 5 23 2 99 10 2
Пример вывода 2
164
