Олимпиадный тренинг

Задача . F. Мышки и норки


Задача

Темы: дп жадные алгоритмы сортировки Структуры данных *2600

Однажды Маша неожиданно вернулась домой и застала n мышей в коридоре своей квартиры. Как и положено девушке, она настолько громко закричала, что мыши в ужасе стали разбегаться по своим норкам.

Коридор можно представить числовой прямой, на которой расположены n мышей и m норок. i-я мышка изначально находится в точке xi, а j-я норка — в точке pj. Вместимость j-й норки составляет cj, то есть в эту норку может поместиться не более cj мышек.

Какой минимальный суммарный путь проделают мышки, чтобы после крика Маши все они спрятались по норкам? Если i-я мышка выберет в качестве укрытия норку j, то пройденный путь следует считать по формуле |xi - pj|.

Выведите минимальный суммарный путь мышек до норок.

Входные данные

В первой строке записаны два целых числа n, m (1 ≤ n, m ≤ 5000) — количество мышек и количество норок соответственно.

Вторая строка содержит последовательность из n целых чисел x1, x2, ..., xn ( - 109 ≤ xi ≤ 109), где xi — начальная координата i-й мышки.

Следующие m строк содержат пары целых чисел — описания норок pj, cj ( - 109 ≤ pj ≤ 109, 1 ≤ cj ≤ 5000), где pj — координата j-й норки, а cj — вместимость j-й норки (в мышках).

Выходные данные

Выведите единственное целое число — минимальный суммарный путь мышек, чтобы каждая мышка оказалась в норке. Выведите -1, если решения не существует.


Примеры
№Входные данныеВыходные данные
1 4 5
6 2 8 9
3 6
2 1
3 6
4 7
4 7 
11
2 7 2
10 20 30 40 50 45 35
-1000000000 10
1000000000 1 
7000000130

time 1500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет