Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2117. Вор
Деревья (map, set), хэш-таблицыОлимпиадные задачи на русском языке
| 16/07/2014 | Лето 2014 - 12 (D) |
| 13/07/2020 | Летние сборы - 7 (E) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Сложная экономическая ситуация в стране и сокращение государственного финансирования
сельского хозяйства вызвали у Мирко желание снова изменить свою карьеру, на этот раз он стал вором.
Свои первые профессиональные усилия он направил на ювелирный магазин.
В магазине есть `N` ювелирных украшений, каждое из них имеет некоторую масса `M_i` и ценность `V_i`.
Мирко имеет `K` мешков для хранения награбленного, и каждый мешок может содержать
некоторую максимальную массу `C_i`.
Мирко планирует унести всю свою добычу в этих мешках, но не более одного ювелирного изделия в каждом мешке,
с тем чтобы уменьшить вероятность их повреждения во время побега.
Найти максимальную общую стоимость ювелирных изделий, которые Мирко может "освободить".
Первая строка входного файла содержит два целых числа `N` и `K` (`1\ ≤\ N,\ K\ ≤\ 300\ 000`).
Каждая из следующих `N` строк содержит пару целых чисел `М_i` и `V_i` (`1\ ≤\ M_i,\ V_i\ ≤\ 1\ 000\ 000`).
Каждая из следующих `K` строк содержит одно целое число `С_i` (`1\ ≤\ C_i\ ≤\ 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
