F. Третья благодать
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Даны $$$n$$$ отрезков и $$$m$$$ точек на числовой прямой. $$$i$$$-й отрезок имеет границы $$$[l_i,r_i]$$$, а $$$i$$$-я точка находится на координате $$$i$$$ и имеет коэффициент $$$p_i$$$.

Изначально все точки неактивны. Вам нужно выбрать подмножество из $$$m$$$ точек для активации. Для каждого из $$$n$$$ интервалов мы определяем его стоимость как:

  • $$$0$$$, если в интервале нет активированных точек;
  • коэффициент активированной точки с наибольшей координатой внутри интервала в противном случае.

Ваша задача — максимизировать сумму стоимостей всех интервалов, выбирая, какие точки активировать.

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

Каждый тест содержит несколько наборов входных данных. Первая строка ввода содержит одно целое число $$$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$$$.

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

Выведите максимально возможную сумму стоимостей всех интервалов.

Пример
Входные данные
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
Примечание

В первом примере мы можем активировать точки $$$1$$$ и $$$8$$$. Сумма стоимостей всех интервалов будет $$$78+30=108$$$.

Во втором примере мы не будем активировать ни одной точки. Сумма стоимостей всех интервалов будет $$$0$$$.