409682: GYM103678 E Бернард и футболки

E. Бернард и футболкиограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Бернард со своей командой выиграл олимпиаду по программированию, и организаторы решили преподнести им невероятно оригинальный подарок — футболки. Проблема в том, что футболки произведены в Берляндии, поэтому всегда сложно угадать их размер. Существует $$$M$$$ размеров футболок, и футболки $$$i$$$-го размера могут с равной вероятностью иметь целочисленную длину в диапазоне от $$$A_i$$$ до $$$B_i$$$ включительно.

Команда Бернарда состоит из $$$N$$$ участников, причем $$$i$$$-й участник желает футболку длины $$$X_i$$$. Жюри олимпиады дает победителям возможность выбрать размер футболок, и все члены команды получают футболки одинаковой целочисленной длины. Значение этой длины заранее неизвестно, но всегда лежит в диапазоне, соответствующем размеру. Бернард хочет выбрать размер так, чтобы минимизировать математическое ожидание средней разницы между желаемой и полученной длиной футболки каждого участника.

Помогите ему сделать выбор.

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

Первая строка входных данных содержит два целых числа $$$N$$$ и $$$M$$$ $$$(1 \le N \le 10^5, 1 \le M \le 10^3)$$$ — количество участников и количество размеров футболок.

Следующая строка содержит $$$N$$$ целых чисел $$$X_i$$$ $$$(1 \le X_i \le 10^9)$$$ — желаемые длины футболок участников.

Следующие $$$M$$$ строк содержат по два целых числа $$$A_j$$$, $$$B_j$$$ $$$(1 \leq A_j \le B_j \leq 10^9)$$$ — диапазон длин футболок $$$j$$$-го размера.

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

Выведите единственное вещественное число — минимальное математическое ожидание средней разницы.

Ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$.

Система оценки

Группа	Доп. ограничения	Баллы	Требуемые подзадачи	Тип проверки
$$$1$$$	$$$N \le 1000$$$, $$$M \le 50$$$, $$$X, A, B \le 1000$$$	$$$30$$$	—	Полная
$$$2$$$	$$$N \le 20000$$$, $$$M \le 500$$$	$$$20$$$	$$$1$$$	Полная
$$$3$$$	—	$$$50$$$	$$$2$$$	Полная

ПримерВходные данные

3 4
4 6 3
2 8
1 9
5 15
3 7

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

1.6000000000