Codeforces Round 875 (Div. 1) |
---|
Закончено |
Даны $$$n$$$ отрезков и $$$m$$$ точек на числовой прямой. $$$i$$$-й отрезок имеет границы $$$[l_i,r_i]$$$, а $$$i$$$-я точка находится на координате $$$i$$$ и имеет коэффициент $$$p_i$$$.
Изначально все точки неактивны. Вам нужно выбрать подмножество из $$$m$$$ точек для активации. Для каждого из $$$n$$$ интервалов мы определяем его стоимость как:
Ваша задача — максимизировать сумму стоимостей всех интервалов, выбирая, какие точки активировать.
Каждый тест содержит несколько наборов входных данных. Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Затем следует описание наборов.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^6, 1 \le m \le 10^6$$$) — количество интервалов и количество точек.
Следующие $$$n$$$ строк каждого набора содержат два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) — концы $$$i$$$-го интервала.
Следующая строка каждого набора содержит $$$m$$$ целых чисел $$$p_1,p_2,\ldots,p_m$$$ ($$$0 \le p_i \le 10^9$$$) — коэффициенты точек.
Гарантируется, что сумма $$$n$$$ не превышает $$$10^6$$$, а сумма $$$m$$$ не превышает $$$10^6$$$.
Выведите максимально возможную сумму стоимостей всех интервалов.
22 81 53 878 0 50 0 0 0 0 301 61 50 0 0 0 0 100
108 0
В первом примере мы можем активировать точки $$$1$$$ и $$$8$$$. Сумма стоимостей всех интервалов будет $$$78+30=108$$$.
Во втором примере мы не будем активировать ни одной точки. Сумма стоимостей всех интервалов будет $$$0$$$.
Название |
---|