F. Мышки и норки
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Маша неожиданно вернулась домой и застала 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, если решения не существует.

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