1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Flights
Contest: Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements)
Difficulty rating: 2600
Tags: graphs, shortest paths

LiLand is a country, consisting of n cities. The cities are numbered from 1 to n. The country is well known because it has a very strange transportation system. There are many one-way flights that make it possible to travel between the cities, but the flights are arranged in a way that once you leave a city you will never be able to return to that city again.

Previously each flight took exactly one hour, but recently Lily has become the new manager of transportation system and she wants to change the duration of some flights. Specifically, she wants to change the duration of some flights to exactly 2 hours in such a way that all trips from city 1 to city n take the same time regardless of their path.

Your task is to help Lily to change the duration of flights.

Input format:
First line of the input contains two integer numbers n and m (2 ≤ n ≤ 1000; 1 ≤ m ≤ 5000) specifying the number of cities and the number of flights.

Each of the next m lines contains two integers ai and bi (1 ≤ ai < bi ≤ n) specifying a one-directional flight from city ai to city bi. It is guaranteed that there exists a way to travel from city number 1 to city number n using the given flights. It is guaranteed that there is no sequence of flights that forms a cyclical path and no two flights are between the same pair of cities.

Output format:
If it is impossible for Lily to do her task, print "No" (without quotes) on the only line of the output.

Otherwise print "Yes" (without quotes) on the first line of output, then print an integer ansi (1 ≤ ansi ≤ 2) to each of the next m lines being the duration of flights in new transportation system. You should print these numbers in the order that flights are given in the input.

If there are multiple solutions for the input, output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 3
1 2
2 3
1 3

Example output:
Yes
1
1
2

Example input:
4 4
1 2
2 3
3 4
1 4

Example output:
No

Editorial:
Challenging Balloons
Contest: Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements)
Difficulty rating: 1900
Tags: constructive algorithms

Martha — as a professional problemsetter — proposed a problem for a world-class contest. This is the problem statement:

Tomorrow is Nadia's birthday, and Bardia (her brother) is assigned to make the balloons ready!

There are n balloons (initially empty) that are tied to a straight line on certain positions x1, x2, ..., xn. Bardia inflates the balloons from left to right. As a result, i-th balloon gets bigger and bigger until its radius reaches the pressure endurance pi or it touches another previously-inflated balloon.

While Bardia was busy with the balloons, he wondered "What will be the sum of radius of balloons after all of the balloons are inflated?". Being a nerdy type of guy, he is now thinking about the problem instead of preparing his sister's birthday. Calculate the answer to Bardia's problem so that Nadia's birthday won't be balloon-less.

Artha — Martha's student — claimed his solution got accepted. Martha (being his teacher for a long time!) knew he couldn't have solved the problem for real and thus thinks there is something wrong with the testcases. Artha isn't anyhow logical, which means there is no way for Martha to explain the wrong point in his algorithm. So, the only way is to find a testcase to prove him wrong!

Artha's pseudo-code is shown below:

You should output a small testcase for the problem such that Artha's algorithm is incorrect. The algorithm's output is considered correct if it differs from the correct value by no more than 1.

Input format:
Please pay attention! No input will be given to your program for this problem. So you do not have to read from the input anything.

Output format:
You should output the generated small testcase (which Artha's solution doesn't get it right). It should be in the following format:

- First line must contain the only number n (1 ≤ n ≤ 500).
- The i-th of the next n lines should contain the description of the i-th balloon — two space-separated integers xi, pi (1 ≤ pi ≤ 106, 0 ≤ x1 < x2 < ... < xn ≤ 106).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The testcase depicted in the figure above (just showing how output should be formatted):

Editorial:
Digit Minimization
Contest: Codeforces Round 792 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, games, math, strings

There is an integer $$$n$$$ without zeros in its decimal representation. Alice and Bob are playing a game with this integer. Alice starts first. They play the game in turns.

On her turn, Alice must swap any two digits of the integer that are on different positions. Bob on his turn always removes the last digit of the integer. The game ends when there is only one digit left.

You have to find the smallest integer Alice can get in the end, if she plays optimally.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first and the only line of each test case contains the integer $$$n$$$ ($$$10 \le n \le 10^9$$$) — the integer for the game. $$$n$$$ does not have zeros in its decimal representation.

Output format:
For each test case output a single integer — the smallest integer Alice can get in the end of the game.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case Alice has to swap $$$1$$$ and $$$2$$$. After that Bob removes the last digit, $$$1$$$, so the answer is $$$2$$$.

In the second test case Alice can swap $$$3$$$ and $$$1$$$: $$$312$$$. After that Bob deletes the last digit: $$$31$$$. Then Alice swaps $$$3$$$ and $$$1$$$: $$$13$$$ and Bob deletes $$$3$$$, so the answer is $$$1$$$.

Example input:
3
12
132
487456398

Example output:
2
1
3

Editorial:
Let $$$k$$$ be the length of $$$n$$$. Let $$$n_i$$$ be the $$$i$$$-th digit of $$$n$$$ ($$$1$$$-indexation from the left).
• $$$k = 1$$$The game ends immediately so the answer is $$$n$$$ itself.
• $$$k = 2$$$Alice should make the first move and she has to swap $$$n_1$$$ and $$$n_2$$$. After that Bob removes $$$n_1$$$ and in the end there is only $$$n_2$$$.
• $$$k \ge 3$$$Alice can make swaps in such way that when there are only two digits left the second digit will be the maximal digit of $$$n$$$. Then she will make a swap and the maximal digit will be on the first position. The other one will be removed by Bob. This way she can always get the maximal digit of $$$n$$$ in the end of the game.
Z mod X = C
Contest: Codeforces Round 792 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, math

You are given three positive integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$a < b < c$$$). You have to find three positive integers $$$x$$$, $$$y$$$, $$$z$$$ such that:

$$$$$$x \bmod y = a,$$$$$$ $$$$$$y \bmod z = b,$$$$$$ $$$$$$z \bmod x = c.$$$$$$

Here $$$p \bmod q$$$ denotes the remainder from dividing $$$p$$$ by $$$q$$$. It is possible to show that for such constraints the answer always exists.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. Description of the test cases follows.

Each test case contains a single line with three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le a < b < c \le 10^8$$$).

Output format:
For each test case output three positive integers $$$x$$$, $$$y$$$, $$$z$$$ ($$$1 \le x, y, z \le 10^{18}$$$) such that $$$x \bmod y = a$$$, $$$y \bmod z = b$$$, $$$z \bmod x = c$$$.

You can output any correct answer.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

$$$$$$x \bmod y = 12 \bmod 11 = 1;$$$$$$

$$$$$$y \bmod z = 11 \bmod 4 = 3;$$$$$$

$$$$$$z \bmod x = 4 \bmod 12 = 4.$$$$$$

Example input:
4
1 3 4
127 234 421
2 7 8
59 94 388

Example output:
12 11 4
1063 234 1484
25 23 8
2221 94 2609

Editorial:
In this problem it is enough to find a contstruction that works for all $$$a < b < c$$$. For example:
In this case
$$$x \bmod y = (a + b + c) \bmod (b + c) = a$$$ since $$$a < b < b + c$$$
$$$y \bmod z = (b + c) \bmod c = b$$$ since $$$b < c$$$
$$$z \bmod x = c \bmod (a + b + c) = c$$$ since $$$c < (a + b + c)$$$.
Column Swapping
Contest: Codeforces Round 792 (Div. 1 + Div. 2)
Difficulty rating: 1400
Tags: brute force, constructive algorithms, greedy, implementation, sortings

You are given a grid with $$$n$$$ rows and $$$m$$$ columns, where each cell has a positive integer written on it. Let's call a grid good, if in each row the sequence of numbers is sorted in a non-decreasing order. It means, that for each $$$1 \le i \le n$$$ and $$$2 \le j \le m$$$ the following holds: $$$a_{i,j} \ge a_{i, j-1}$$$.

You have to to do the following operation exactly once: choose two columns with indexes $$$i$$$ and $$$j$$$ (not necessarily different), $$$1 \le i, j \le m$$$, and swap them.

You are asked to determine whether it is possible to make the grid good after the swap and, if it is, find the columns that need to be swapped.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of rows and columns respectively.

Each of the next $$$n$$$ rows contains $$$m$$$ integers, $$$j$$$-th element of $$$i$$$-th row is $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — the number written in the $$$j$$$-th cell of the $$$i$$$-th row.

It's guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
If after the swap it is impossible to get a good grid, output $$$-1$$$.

In the other case output $$$2$$$ integers — the indices of the columns that should be swapped to get a good grid.

If there are multiple solutions, print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case the grid is initially good, so we can, for example, swap the first column with itself.

In the second test case it is impossible to make the grid good.

In the third test case it is needed to swap the first and the second column, then the grid becomes good.

Example input:
5
2 3
1 2 3
1 1 1
2 2
4 1
2 3
2 2
2 1
1 1
2 3
6 2 1
5 4 3
2 1
1
2

Example output:
1 1
-1
1 2
1 3
1 1

Editorial:
At first, let's check wether the given table is good. If it is not then there is a row that has elements that should be replaced.
Let's say that this row is $$$a$$$ and $$$b$$$ is the sorted row $$$a$$$. Then let's find the set of positions $$$i$$$ that $$$a_i \neq b_i$$$. If there are at least $$$3$$$ such positions then the answer is $$$-1$$$ because by making a swap we remove at most $$$2$$$ such bad positions. If there are no more than $$$2$$$ such positions then let's swap the corresponding columns and check whether each row is sorted. If the table is good we found the answer. If it is not then the answer is $$$-1$$$ because we can not sort $$$a$$$ and get a good table after that.
Copil Copac Draws Trees
Contest: Codeforces Round 875 (Div. 1)
Difficulty rating: 1400
Tags: dfs and similar, dp, graphs, trees

Copil Copac is given a list of $$$n-1$$$ edges describing a tree of $$$n$$$ vertices. He decides to draw it using the following algorithm:

- Step $$$0$$$: Draws the first vertex (vertex $$$1$$$). Go to step $$$1$$$.
- Step $$$1$$$: For every edge in the input, in order: if the edge connects an already drawn vertex $$$u$$$ to an undrawn vertex $$$v$$$, he will draw the undrawn vertex $$$v$$$ and the edge. After checking every edge, go to step $$$2$$$.
- Step $$$2$$$: If all the vertices are drawn, terminate the algorithm. Else, go to step $$$1$$$.

The number of readings is defined as the number of times Copil Copac performs step $$$1$$$.

Find the number of readings needed by Copil Copac to draw the tree.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices of the tree.

The following $$$n - 1$$$ lines of each test case contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — indicating that $$$(u_i,v_i)$$$ is the $$$i$$$-th edge in the list. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the number of readings Copil Copac needs to draw the tree.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

After the first reading, the tree will look like this:

After the second reading:

Therefore, Copil Copac needs $$$2$$$ readings to draw the tree.

Example input:
2
6
4 5
1 3
1 2
3 4
1 6
7
5 6
2 4
2 7
1 3
1 2
4 5

Example output:
2
3

Editorial:
The BOSS Can Count Pairs
Contest: Codeforces Round 875 (Div. 1)
Difficulty rating: 2000
Tags: brute force, math

You are given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$.

Your task is to count the number of pairs of integers $$$(i,j)$$$ such that $$$1 \leq i < j \leq n$$$ and $$$a_i \cdot a_j = b_i+b_j$$$.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the arrays.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \le b_i \le n$$$) — the elements of array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the number of good pairs.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first sample, there are $$$2$$$ good pairs:

- $$$(1,2)$$$,
- $$$(1,3)$$$.

In the second sample, there are $$$7$$$ good pairs:

- $$$(1,2)$$$,
- $$$(1,5)$$$,
- $$$(2,8)$$$,
- $$$(3,4)$$$,
- $$$(4,7)$$$,
- $$$(5,6)$$$,
- $$$(5,7)$$$.

Example input:
3
3
2 3 2
3 3 1
8
4 2 8 2 1 2 7 5
3 5 8 8 1 1 6 5
8
4 4 8 8 8 8 8 8
8 8 8 8 8 8 8 8

Example output:
2
7
1

Editorial:
Hyperregular Bracket Strings
Contest: Codeforces Round 875 (Div. 1)
Difficulty rating: 2400
Tags: combinatorics, greedy, hashing, math, number theory, sortings

You are given an integer $$$n$$$ and $$$k$$$ intervals. The $$$i$$$-th interval is $$$[l_i,r_i]$$$ where $$$1 \leq l_i \leq r_i \leq n$$$.

Let us call a regular bracket sequence$$$^{\dagger,\ddagger}$$$ of length $$$n$$$ hyperregular if for each $$$i$$$ such that $$$1 \leq i \leq k$$$, the substring $$$\overline{s_{l_i} s_{l_{i}+1} \ldots s_{r_i}}$$$ is also a regular bracket sequence.

Your task is to count the number of hyperregular bracket sequences. Since this number can be really large, you are only required to find it modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A bracket sequence is a string containing only the characters "(" and ")".

$$$^\ddagger$$$ A bracket sequence is called regular if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are regular, while )(, ((), and (()))( are not.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$0 \le k \le 3 \cdot 10^5$$$) — the length of the hyperregular bracket sequences and the number of intervals respectively.

The following $$$k$$$ lines of each test case contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l \le r \le n$$$).

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$ and the sum of $$$k$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output the number of hyperregular bracket sequences modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
- For the first testcase, the $$$5$$$ hyperregular bracket strings of length $$$6$$$ are: ((())), (()()), (())(), ()(()) and ()()().
- For the second testcase, there are no regular bracket strings of length $$$5$$$, and consequently, there are no hyperregular bracket strings of length $$$5$$$.
- For the third testcase, there are no hyperregular bracket strings of length $$$8$$$ for which the substring $$$[1 \ldots 3]$$$ is a regular bracket string.
- For the fourth testcase, there $$$4$$$ hyperregular bracket strings are: ((())(())), ((())()()), ()()((())) and ()()(()())

Example input:
7
6 0
5 0
8 1
1 3
10 2
3 4
6 9
1000 3
100 701
200 801
300 901
28 5
1 12
3 20
11 14
4 9
18 19
4 3
1 4
1 4
1 4

Example output:
5
0
0
4
839415253
140
2

Editorial:
Mex Tree
Contest: Codeforces Round 875 (Div. 1)
Difficulty rating: 2800
Tags: brute force, dp, trees

You are given a tree with $$$n$$$ nodes. For each node, you either color it in $$$0$$$ or $$$1$$$.

The value of a path $$$(u,v)$$$ is equal to the MEX$$$^\dagger$$$ of the colors of the nodes from the shortest path between $$$u$$$ and $$$v$$$.

The value of a coloring is equal to the sum of values of all paths $$$(u,v)$$$ such that $$$1 \leq u \leq v \leq n$$$.

What is the maximum possible value of any coloring of the tree?

$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of nodes in the tree.

The following $$$n-1$$$ lines of each test case contains $$$2$$$ integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) — indicating an edge between vertices $$$a_i$$$ and $$$b_i$$$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print the maximum possible value of any coloring of the tree.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample, we will color vertex $$$2$$$ in $$$1$$$ and vertices $$$1,3$$$ in $$$0$$$. After this, we consider all paths:

- $$$(1,1)$$$ with value $$$1$$$
- $$$(1,2)$$$ with value $$$2$$$
- $$$(1,3)$$$ with value $$$2$$$
- $$$(2,2)$$$ with value $$$0$$$
- $$$(2,3)$$$ with value $$$2$$$
- $$$(3,3)$$$ with value $$$1$$$

We notice the sum of values is $$$8$$$ which is the maximum possible.

Example input:
4
3
1 2
2 3
4
1 2
1 3
1 4
10
1 2
1 3
3 4
3 5
1 6
5 7
2 8
6 9
6 10
1

Example output:
8
15
96
1

Editorial:
Bully Sort
Contest: Codeforces Round 875 (Div. 1)
Difficulty rating: 3500
Tags: data structures, math

On a permutation $$$p$$$ of length $$$n$$$, we define a bully swap as follows:

- Let $$$i$$$ be the index of the largest element $$$p_i$$$ such that $$$p_i \neq i$$$.
- Let $$$j$$$ be the index of the smallest element $$$p_j$$$ such that $$$i < j$$$.
- Swap $$$p_i$$$ and $$$p_j$$$.

We define $$$f(p)$$$ as the number of bully swaps we need to perform until $$$p$$$ becomes sorted. Note that if $$$p$$$ is the identity permutation, $$$f(p)=0$$$.

You are given $$$n$$$ and a permutation $$$p$$$ of length $$$n$$$. You need to process the following $$$q$$$ updates.

In each update, you are given two integers $$$x$$$ and $$$y$$$. You will swap $$$p_x$$$ and $$$p_y$$$ and then find the value of $$$f(p)$$$.

Note that the updates are persistent. Changes made to the permutation $$$p$$$ will apply when processing future updates.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 5 \cdot 10^5$$$, $$$1 \le q \le 5 \cdot 10^4$$$) — the length of the permutation and the number of updates.

The second line of input contains $$$n$$$ integer $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$. All elements of $$$p$$$ are distinct.

The $$$i$$$-th of the next $$$q$$$ lines of input contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i < y_i \le n$$$) — describing the $$$i$$$-th update.

Output format:
After each update, output $$$f(p)$$$.

Constraints:
Time limit: 10.0 s
Memory limit: 1024.0 MB

Note:
After the first update, we have $$$f(p)=5$$$. The $$$5$$$ bully swaps are illustrated below.

- $$$[\mathbf{1}, 2, \mathbf{8}, 5, 3, 4, 7, 6]$$$,
- $$$[1, 2, \mathbf{3}, 5, \mathbf{8}, 4, 7, 6]$$$,
- $$$[1, 2, 3, 5, \mathbf{4}, \mathbf{8}, 7, 6]$$$,
- $$$[1, 2, 3, 5, 4, \mathbf{6}, 7, \mathbf{8}]$$$,
- $$$[1, 2, 3, \mathbf{4}, \mathbf{5}, 6, 7, 8]$$$.

Example input:
8 5
6 2 1 5 3 4 7 8
1 8
2 3
4 7
7 8
3 6

Example output:
5
6
9
8
7

Editorial:
The Third Grace
Contest: Codeforces Round 875 (Div. 1)
Difficulty rating: 3200
Tags: data structures, dp

You are given $$$n$$$ intervals and $$$m$$$ points on the number line. The $$$i$$$-th intervals covers coordinates $$$[l_i,r_i]$$$ and the $$$i$$$-th point is on coordinate $$$i$$$ and has coefficient $$$p_i$$$.

Initially, all points are not activated. You should choose a subset of the $$$m$$$ points to activate. For each of $$$n$$$ interval, we define its cost as:

- $$$0$$$, if there are no activated points in the interval;
- the coefficient of the activated point with the largest coordinate within it, otherwise.

Your task is to maximize the sum of the costs of all intervals by choosing which points to activate.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^6, 1 \le m \le 10^6$$$) — the number of intervals and the number of points.

The following $$$n$$$ lines of each test case contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) — the endpoints of the $$$i$$$-th interval.

The following line of each test case contains $$$m$$$ integers $$$p_1,p_2,\ldots,p_m$$$ ($$$0 \le p_i \le 10^9$$$) — the coefficients of the points.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$10^6$$$ and the sum of $$$m$$$ does not exceed $$$10^6$$$.

Output format:
Output the maximum possible sum of costs of all intervals.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Note:
In the first sample, we can activate points $$$1$$$ and $$$8$$$. The sum of costs of all intervals will be $$$78+30=108$$$.

In the second sample, we will activate no points. The sum of costs of all intervals will be $$$0$$$.

Example input:
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

Example output:
108
0

Editorial: