Поликарп живет на координатной прямой в точке \(x = 0\). Он отправился в гости к своему другу, который живет в точке \(x = a\). Поликарп двигается только слева направо, преодолевает одну единицу длины за одну секунду.
В настоящий момент идет дождь, поэтому некоторые участки его пути находятся под дождем. Формально: дождь льет на \(n\) непересекающихся отрезках, \(i\)-й отрезок под дождем имеет вид \([l_i, r_i]\) (\(0 \le l_i < r_i \le a\)).
На координатной прямой есть \(m\) зонтиков, \(i\)-й зонтик расположен в точке \(x_i\) (\(0 \le x_i \le a\)) и имеет массу \(p_i\). В начале своего путешествия Поликарп не несет ни одного зонтика.
По пути из \(x = 0\) в \(x = a\) Поликарп может подбирать и оставлять зонтики. Как подбор, так и сброс зонтика осуществляется мгновенно. Поликарп может нести произвольное количество зонтиков одновременно. Так как Поликарп не хочет промокнуть, то при перемещении из \(x\) в \(x + 1\) он должен обязательно нести хотя бы один зонтик, если отрезок \([x, x + 1]\) находится под дождем (то есть существует такое \(i\), что \(l_i \le x\) и \(x + 1 \le r_i\)).
Написанное выше условие — единственное требование к маршруту Поликарпа. Например, допустимо дойти без зонтика до точки, в которой начинается дождь, подобрать в этой точке зонтик и продолжить путь уже под зонтиком. Например, Поликарп может сменить зонтик, находясь под дождем — подобрать новый зонтик и одновременно оставить старый, находясь в промежуточной точке участка под дождем.
При каждом перемещении на единицу вправо к усталости Поликарпа прибавляется суммарная масса всех зонтиков, которые он несет.
Сможет ли Поликарп добраться из точки \(x = 0\) в точку \(x = a\)? В случае положительного ответа найдите наименьшую суммарную усталость, с которой Поликарп придет в точку \(x = a\), если будет подбирать и оставлять зонтики оптимальным образом.
Выходные данные
Выведите «-1» (без кавычек), если Поликарп не сможет добраться из точки \(x = 0\) в точку \(x = a\). Иначе выведите одно целое число — наименьшую суммарную усталость, с которой Поликарп придет в точку \(x = a\), если будет подбирать и оставлять зонтики оптимальным образом.
Примечание
В первом тестовом примере единственная возможная стратегия — взять четвертый зонтик в точке \(x = 1\) и идти с ним до точки \(x = 7\) (суммарная усталость в точке \(x = 7\) будет равна \(12\)), оставить его, пройти от \(x = 7\) до \(x = 8\) без зонтика, взять третий зонтик в точке \(x = 8\) и идти с ним до конца (суммарная усталость в точке \(x = 10\) будет равна \(14\)).
Во втором тестовом примере единственная возможная стратегия — взять первый зонтик, пройти с ним до точки \(x = 9\), выбросить его и завершить путь без зонтика.