Даны \(n\) отрезков и \(m\) точек на числовой прямой. \(i\)-й отрезок имеет границы \([l_i,r_i]\), а \(i\)-я точка находится на координате \(i\) и имеет коэффициент \(p_i\).
Изначально все точки неактивны. Вам нужно выбрать подмножество из \(m\) точек для активации. Для каждого из \(n\) интервалов мы определяем его стоимость как:
- \(0\), если в интервале нет активированных точек;
- коэффициент активированной точки с наибольшей координатой внутри интервала в противном случае.
Ваша задача — максимизировать сумму стоимостей всех интервалов, выбирая, какие точки активировать.
Выходные данные
Выведите максимально возможную сумму стоимостей всех интервалов.
Примечание
В первом примере мы можем активировать точки \(1\) и \(8\). Сумма стоимостей всех интервалов будет \(78+30=108\).
Во втором примере мы не будем активировать ни одной точки. Сумма стоимостей всех интервалов будет \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 8
1 5
3 8
78 0 50 0 0 0 0 30
1 6
1 5
0 0 0 0 0 100
|
108
0
|