print2117. Вор

printВор

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
Source: COCI 2013/2014, contest #1
loading