yl-9/probench huggingface dataset:
# Court Blue (Hard Version)

## Problem Description

This is the hard version of the problem. In this version, it is not guaranteed that $ n=m $ , and the time limit is higher. You can make hacks only if both versions of the problem are solved.

In the court of the Blue King, Lelle and Flamm are having a performance match. The match consists of several rounds. In each round, either Lelle or Flamm wins.

Let $ W_L $ and $ W_F $ denote the number of wins of Lelle and Flamm, respectively. The Blue King considers a match to be successful if and only if:

- after every round, $ \gcd(W_L,W_F)\le 1 $ ;
- at the end of the match, $ W_L\le n, W_F\le m $ .

Note that $ \gcd(0,x)=\gcd(x,0)=x $ for every non-negative integer $ x $ .

Lelle and Flamm can decide to stop the match whenever they want, and the final score of the performance is $ l \cdot W_L + f \cdot W_F $ .

Please help Lelle and Flamm coordinate their wins and losses such that the performance is successful, and the total score of the performance is maximized.

## Input Format

The first line contains an integer $ t $ ( $ 1\leq t \leq 10^3 $ ) — the number of test cases.

The only line of each test case contains four integers $ n $ , $ m $ , $ l $ , $ f $ ( $ 2\leq n\leq m \leq 2\cdot 10^7 $ , $ 1\leq l,f \leq 10^9 $ ): $ n $ , $ m $ give the upper bound on the number of Lelle and Flamm's wins, $ l $ and $ f $ determine the final score of the performance.

Unusual additional constraint: it is guaranteed that, for each test, there are no pairs of test cases with the same pair of $ n $ , $ m $ .

## Output Format

For each test case, output a single integer — the maximum total score of a successful performance.

## Sample #1

### Sample Input #1

```
8
3 4 2 5
4 4 1 4
6 6 2 2
7 9 2 3
8 9 9 1
2 7 1 4
5 9 1 4
5 6 6 7
```

### Sample Output #1

```
22
17
18
37
77
30
41
59
```

## Sample #2

### Sample Input #2

```
2
3082823 20000000 1341 331
20000000 20000000 3 5
```

### Sample Output #2

```
10754065643
159999991
```

## Sample #3

### Sample Input #3

```
1
139 1293 193 412
```

### Sample Output #3

```
559543
```

## Hint

In the first test case, a possible performance is as follows:

- Flamm wins, $ \gcd(0,1)=1 $ .
- Lelle wins, $ \gcd(1,1)=1 $ .
- Flamm wins, $ \gcd(1,2)=1 $ .
- Flamm wins, $ \gcd(1,3)=1 $ .
- Flamm wins, $ \gcd(1,4)=1 $ .
- Lelle and Flamm agree to stop the match.

The final score is $ 1\cdot2+4\cdot5=22 $ .

## Limit



Time Limit
4.00s

Memory Limit
500.00MB

Tags: brute force, dp, math, number theory
Difficulty: 2800
# Court Blue (Easy Version)

## Problem Description

This is the easy version of the problem. In this version, $ n=m $ and the time limit is lower. You can make hacks only if both versions of the problem are solved.

In the court of the Blue King, Lelle and Flamm are having a performance match. The match consists of several rounds. In each round, either Lelle or Flamm wins.

Let $ W_L $ and $ W_F $ denote the number of wins of Lelle and Flamm, respectively. The Blue King considers a match to be successful if and only if:

- after every round, $ \gcd(W_L,W_F)\le 1 $ ;
- at the end of the match, $ W_L\le n, W_F\le m $ .

Note that $ \gcd(0,x)=\gcd(x,0)=x $ for every non-negative integer $ x $ .

Lelle and Flamm can decide to stop the match whenever they want, and the final score of the performance is $ l \cdot W_L + f \cdot W_F $ .

Please help Lelle and Flamm coordinate their wins and losses such that the performance is successful, and the total score of the performance is maximized.

## Input Format

The first line contains an integer $ t $ ( $ 1\leq t \leq 10^3 $ ) — the number of test cases.

The only line of each test case contains four integers $ n $ , $ m $ , $ l $ , $ f $ ( $ 2\leq n\leq m \leq 2\cdot 10^7 $ , $ 1\leq l,f \leq 10^9 $ , $ \bf{n=m} $ ): $ n $ , $ m $ gives the upper bound on the number of Lelle and Flamm's wins, $ l $ and $ f $ determine the final score of the performance.

Unusual additional constraint: it is guaranteed that, for each test, there are no pairs of test cases with the same pair of $ n $ , $ m $ .

## Output Format

For each test case, output a single integer — the maximum total score of a successful performance.

## Sample #1

### Sample Input #1

```
8
3 3 2 5
4 4 1 4
6 6 2 2
7 7 2 3
9 9 9 1
2 2 1 4
5 5 1 4
8 8 6 7
```

### Sample Output #1

```
19
17
18
33
86
9
24
86
```

## Sample #2

### Sample Input #2

```
1
20000000 20000000 1341 331
```

### Sample Output #2

```
33439999007
```

## Sample #3

### Sample Input #3

```
2
1984 1984 19 84
9982 9982 44 35
```

### Sample Output #3

```
204143
788403
```

## Hint

In the first test case, a possible performance is as follows:

- Flamm wins, $ \gcd(0,1)=1 $ .
- Lelle wins, $ \gcd(1,1)=1 $ .
- Flamm wins, $ \gcd(1,2)=1 $ .
- Flamm wins, $ \gcd(1,3)=1 $ .
- Lelle wins, $ \gcd(2,3)=1 $ .
- Lelle and Flamm agree to stop the match.

The final score is $ 2\cdot2+3\cdot5=19 $ .

In the third test case, a possible performance is as follows:

- Flamm wins, $ \gcd(0,1)=1 $ .
- Lelle wins, $ \gcd(1,1)=1 $ .
- Lelle wins, $ \gcd(2,1)=1 $ .
- Lelle wins, $ \gcd(3,1)=1 $ .
- Lelle wins, $ \gcd(4,1)=1 $ .
- Lelle wins, $ \gcd(5,1)=1 $ .
- Flamm wins, $ \gcd(5,2)=1 $ .
- Flamm wins, $ \gcd(5,3)=1 $ .
- Flamm wins, $ \gcd(5,4)=1 $ .
- Lelle and Flamm agree to stop the match.

The final score is $ 5\cdot2+4\cdot2=18 $ . Note that Lelle and Flamm can stop the match even if neither of them has $ n $ wins.

## Limit



Time Limit
3.00s

Memory Limit
500.00MB

Tags: brute force, dfs and similar, dp, math, number theory
Difficulty: 2600
# Cosmic Rays

## Problem Description

Given an array of integers $ s_1, s_2, \ldots, s_l $ , every second, cosmic rays will cause all $ s_i $ such that $ i=1 $ or $ s_i\neq s_{i-1} $ to be deleted simultaneously, and the remaining parts will be concatenated together in order to form the new array $ s_1, s_2, \ldots, s_{l'} $ .

Define the strength of an array as the number of seconds it takes to become empty.

You are given an array of integers compressed in the form of $ n $ pairs that describe the array left to right. Each pair $ (a_i,b_i) $ represents $ a_i $ copies of $ b_i $ , i.e. $ \underbrace{b_i,b_i,\cdots,b_i}_{a_i\textrm{ times}} $ .

For each $ i=1,2,\dots,n $ , please find the strength of the sequence described by the first $ i $ pairs.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\le t\le10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1\le n\le3\cdot10^5 $ ) — the length of sequence $ a $ .

The next $ n $ lines contain two integers each $ a_i $ , $ b_i $ ( $ 1\le a_i\le10^9,0\le b_i\le n $ ) — the pairs which describe the sequence.

It is guaranteed that the sum of all $ n $ does not exceed $ 3\cdot10^5 $ .

It is guaranteed that for all $ 1\le i<n $ , $ b_i\neq b_{i+1} $ holds.

## Output Format

For each test case, print one line containing $ n $ integers — the answer for each prefix of pairs.

## Sample #1

### Sample Input #1

```
4
4
2 0
1 1
3 0
5 1
6
4 6
1 3
4 6
4 0
7 6
6 3
7
9 0
7 1
5 0
7 1
9 0
1 1
2 0
10
10 7
4 9
2 2
7 9
2 8
8 5
11 7
15 5
12 7
4 0
```

### Sample Output #1

```
2 2 4 5 
4 4 7 7 10 10 
9 9 9 9 9 9 10 
10 10 10 10 10 10 12 15 15 15
```

## Hint

In the first test case, for the prefix of length $ 4 $ , the changes will be $ [0,0,1,0,0,0,1,1,1,1,1]\rightarrow[0,0,0,1,1,1,1]\rightarrow[0,0,1,1,1]\rightarrow[0,1,1]\rightarrow[1]\rightarrow[] $ , so the array becomes empty after $ 5 $ seconds.

In the second test case, for the prefix of length $ 4 $ , the changes will be $ [6,6,6,6,3,6,6,6,6,0,0,0,0]\rightarrow[6,6,6,6,6,6,0,0,0]\rightarrow[6,6,6,6,6,0,0]\rightarrow[6,6,6,6,0]\rightarrow[6,6,6]\rightarrow[6,6]\rightarrow[6]\rightarrow[] $ , so the array becomes empty after $ 7 $ seconds.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: brute force, data structures, dp
Difficulty: 2300
# Black Circles

## Problem Description

There are $ n $ circles on a two-dimensional plane. The $ i $ -th circle is centered at $ (x_i,y_i) $ . Initially, all circles have a radius of $ 0 $ .

The circles' radii increase at a rate of $ 1 $ unit per second.

You are currently at $ (x_s,y_s) $ ; your goal is to reach $ (x_t,y_t) $ without touching the circumference of any circle (including the moment you reach $ (x_t,y_t) $ ). You can move in any direction you want. However, your speed is limited to $ 1 $ unit per second.

Please determine whether this is possible.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\le t\le10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1\le n\le10^5 $ ) — the number of circles.

The next $ n $ lines each contain two integers $ x_i $ , $ y_i $ ( $ 1\le x_i,y_i\le10^9 $ ) — the center of each circle.

The final line contains four integers $ x_s $ , $ y_s $ , $ x_t $ , $ y_t $ ( $ 1\le x_s,y_s,x_t,y_t\le10^9 $ ) — the coordinates of the starting point and the goal, respectively.

It is guaranteed that these $ n+2 $ points are distinct.

It is guaranteed that the sum of $ n $ over all testcases does not exceed $ 10^5 $ .

## Output Format

For each test case, output $ \texttt{YES} $ if it is possible to reach the goal without touching the circle boundaries, and output $ \texttt{NO} $ otherwise.

You can output $ \texttt{Yes} $ and $ \texttt{No} $ in any case (for example, strings $ \texttt{yEs} $ , $ \texttt{yes} $ , $ \texttt{Yes} $ , and $ \texttt{YES} $ will be recognized as a positive response).

## Sample #1

### Sample Input #1

```
7
3
2 5
2 14
10 13
4 9 9 7
3
10 11
6 9
12 12
14 13 4 8
1
5 7
12 6 11 13
2
1000000000 2
2 1000000000
1 1 2 2
1
999999998 1000000000
999999999 999999999 1 1
1
1000000000 1
1 1000000000 1 1
10
989237121 2397081
206669655 527238537
522705783 380636165
532545346 320061691
207818728 199485303
884520552 315781807
992311437 802563521
205138355 324818663
223575704 395073023
281560523 236279118
216941610 572010615 323956540 794523071
```

### Sample Output #1

```
YES
NO
YES
YES
YES
NO
YES
```

## Hint

In the first test case, a feasible way of movement is as follows.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2002C/e91b557a5335aaaa3689cd6df137ea06f9152e48.png)

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, geometry, greedy, math
Difficulty: 1200
# Removals Game

## Problem Description

Alice got a permutation $ a_1, a_2, \ldots, a_n $ of $ [1,2,\ldots,n] $ , and Bob got another permutation $ b_1, b_2, \ldots, b_n $ of $ [1,2,\ldots,n] $ . They are going to play a game with these arrays.

In each turn, the following events happen in order:

- Alice chooses either the first or the last element of her array and removes it from the array;
- Bob chooses either the first or the last element of his array and removes it from the array.

The game continues for $ n-1 $ turns, after which both arrays will have exactly one remaining element: $ x $ in the array $ a $ and $ y $ in the array $ b $ .

If $ x=y $ , Bob wins; otherwise, Alice wins. Find which player will win if both players play optimally.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\le t\le10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 3\cdot 10^5 $ ).

The next line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le n $ , all $ a_i $ are distinct) — the permutation of Alice.

The next line contains $ n $ integers $ b_1,b_2,\ldots,b_n $ ( $ 1\le b_i\le n $ , all $ b_i $ are distinct) — the permutation of Bob.

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

## Output Format

For each test case, print a single line with the name of the winner, assuming both players play optimally. If Alice wins, print $ \texttt{Alice} $ ; otherwise, print $ \texttt{Bob} $ .

## Sample #1

### Sample Input #1

```
2
2
1 2
1 2
3
1 2 3
2 3 1
```

### Sample Output #1

```
Bob
Alice
```

## Hint

In the first test case, Bob can win the game by deleting the same element as Alice did.

In the second test case, Alice can delete $ 3 $ in the first turn, and then in the second turn, delete the element that is different from the one Bob deleted in the first turn to win the game.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, games
Difficulty: 1000
# Distanced Coloring

## Problem Description

You received an $ n\times m $ grid from a mysterious source. The source also gave you a magic positive integer constant $ k $ .

The source told you to color the grid with some colors, satisfying the following condition:

- If $ (x_1,y_1) $ , $ (x_2,y_2) $ are two distinct cells with the same color, then $ \max(|x_1-x_2|,|y_1-y_2|)\ge k $ .

You don't like using too many colors. Please find the minimum number of colors needed to color the grid.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\le t\le1000 $ ). The description of the test cases follows.

The only line of each test case consists of three positive integers $ n $ , $ m $ , $ k $ ( $ 1\le n,m,k\le10^4 $ ) — the dimensions of the grid and the magic constant.

## Output Format

For each test case, print a single integer — the minimum number of colors needed to color the grid.

## Sample #1

### Sample Input #1

```
6
3 3 2
5 1 10000
7 3 4
3 2 7
8 9 6
2 5 4
```

### Sample Output #1

```
4
5
12
6
36
8
```

## Hint

In the first test case, one of the optimal constructions is:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2002A/9ce95b69207ca02098572c656648bb834e503b1e.png)In the second test case, the color of all cells must be pairwise different, so the answer is $ 5 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, implementation, math
Difficulty: 800
# Longest Max Min Subsequence

## Problem Description

You are given an integer sequence $ a_1, a_2, \ldots, a_n $ . Let $ S $ be the set of all possible non-empty subsequences of $ a $ without duplicate elements. Your goal is to find the longest sequence in $ S $ . If there are multiple of them, find the one that minimizes lexicographical order after multiplying terms at odd positions by $ -1 $ .

For example, given $ a = [3, 2, 3, 1] $ , $ S = \{[1], [2], [3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 3, 1], [3, 2, 1]\} $ . Then $ [2, 3, 1] $ and $ [3, 2, 1] $ would be the longest, and $ [3, 2, 1] $ would be the answer since $ [-3, 2, -1] $ is lexicographically smaller than $ [-2, 3, -1] $ .

A sequence $ c $ is a subsequence of a sequence $ d $ if $ c $ can be obtained from $ d $ by the deletion of several (possibly, zero or all) elements.

A sequence $ c $ is lexicographically smaller than a sequence $ d $ if and only if one of the following holds:

- $ c $ is a prefix of $ d $ , but $ c \ne d $ ;
- in the first position where $ c $ and $ d $ differ, the sequence $ c $ has a smaller element than the corresponding element in $ d $ .

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5 \cdot 10^4 $ ). The description of the test cases follows.

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

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

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

## Output Format

For each test case, output the answer in the following format:

Output an integer $ m $ in the first line — the length of $ b $ .

Then output $ m $ integers $ b_1, b_2, \ldots, b_m $ in the second line — the sequence $ b $ .

## Sample #1

### Sample Input #1

```
4
4
3 2 1 3
4
1 1 1 1
9
3 2 1 3 2 1 3 2 1
1
1
```

### Sample Output #1

```
3
3 2 1
1
1
3
3 1 2
1
1
```

## Sample #2

### Sample Input #2

```
10
2
1 2
10
5 2 1 7 9 7 2 5 5 2
2
1 2
10
2 2 8 7 7 9 8 1 9 6
9
9 1 7 5 8 5 6 4 1
3
3 3 3
6
1 6 4 4 6 5
6
3 4 4 5 3 3
10
4 1 4 5 4 5 10 1 5 1
7
1 2 1 3 2 4 6
```

### Sample Output #2

```
2
1 2
5
5 1 9 7 2
2
1 2
6
2 7 9 8 1 6
7
9 1 7 5 8 6 4
1
3
4
1 4 6 5
3
4 5 3
4
5 4 10 1
5
2 1 3 4 6
```

## Hint

In the first example, $ S = \{[1], [2], [3], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 1, 3], [3, 2, 1]\} $ . Among them, $ [2, 1, 3] $ and $ [3, 2, 1] $ are the longest and $ [-3, 2, -1] $ is lexicographical smaller than $ [-2, 1, -3] $ , so $ [3, 2, 1] $ is the answer.

In the second example, $ S = \{[1]\} $ , so $ [1] $ is the answer.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, data structures, greedy, implementation
Difficulty: 1900
# Make All Equal

## Problem Description

You are given a cyclic array $ a_1, a_2, \ldots, a_n $ .

You can perform the following operation on $ a $ at most $ n - 1 $ times:

- Let $ m $ be the current size of $ a $ , you can choose any two adjacent elements where the previous one is no greater than the latter one (In particular, $ a_m $ and $ a_1 $ are adjacent and $ a_m $ is the previous one), and delete exactly one of them. In other words, choose an integer $ i $ ( $ 1 \leq i \leq m $ ) where $ a_i \leq a_{(i \bmod m) + 1} $ holds, and delete exactly one of $ a_i $ or $ a_{(i \bmod m) + 1} $ from $ a $ .

Your goal is to find the minimum number of operations needed to make all elements in $ a $ equal.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the length of the array $ a $ .

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 $ .

## Output Format

For each test case, output a single line containing an integer: the minimum number of operations needed to make all elements in $ a $ equal.

## Sample #1

### Sample Input #1

```
7
1
1
3
1 2 3
3
1 2 2
5
5 4 3 2 1
6
1 1 2 2 3 3
8
8 7 6 3 8 7 6 3
6
1 1 4 5 1 4
```

### Sample Output #1

```
0
2
1
4
4
6
3
```

## Hint

In the first test case, there is only one element in $ a $ , so we can't do any operation.

In the second test case, we can perform the following operations to make all elements in $ a $ equal:

- choose $ i = 2 $ , delete $ a_3 $ , then $ a $ would become $ [1, 2] $ .
- choose $ i = 1 $ , delete $ a_1 $ , then $ a $ would become $ [2] $ .

It can be proven that we can't make all elements in $ a $ equal using fewer than $ 2 $ operations, so the answer is $ 2 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, implementation
Difficulty: 800
# Ksyusha and the Loaded Set

## Problem Description

Ksyusha decided to start a game development company. To stand out among competitors and achieve success, she decided to write her own game engine. The engine must support a set initially consisting of $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ .

The set will undergo $ m $ operations sequentially. The operations can be of the following types:

- Insert element $ x $ into the set;
- Remove element $ x $ from the set;
- Report the $ k $ -load of the set.

The $ k $ -load of the set is defined as the minimum positive integer $ d $ such that the integers $ d, d + 1, \ldots, d + (k - 1) $ do not appear in this set. For example, the $ 3 $ -load of the set $ \{3, 4, 6, 11\} $ is $ 7 $ , since the integers $ 7, 8, 9 $ are absent from the set, and no smaller value fits.

Ksyusha is busy with management tasks, so you will have to write the engine. Implement efficient support for the described operations.

## Input Format

The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The following lines describe the test cases.

The first line contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the initial size of the set.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_1 < a_2 < \ldots < a_n \le 2 \cdot 10^6 $ ) — the initial state of the set.

The third line contains an integer $ m $ ( $ 1 \le m \le 2 \cdot 10^5 $ ) — the number of operations.

The next $ m $ lines contain the operations. The operations are given in the following format:

- + $ x $ ( $ 1 \le x \le 2 \cdot 10^6 $ ) — insert element $ x $ into the set (it is guaranteed that $ x $ is not in the set);
- - $ x $ ( $ 1 \le x \le 2 \cdot 10^6 $ ) — remove element $ x $ from the set (it is guaranteed that $ x $ is in the set);
- ? $ k $ ( $ 1 \le k \le 2 \cdot 10^6 $ ) — output the value of the $ k $ -load of the set.

It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ , and the same holds for $ m $ .

## Output Format

For each test case, output the answers to the operations of type "?".

## Sample #1

### Sample Input #1

```
3
5
1 2 5 905 2000000
15
- 2
? 2
? 1
- 1
? 1
+ 4
+ 2
? 2
+ 6
- 4
+ 7
? 2
? 3
? 4
? 2000000
5
3 4 5 6 8
9
? 5
- 5
? 5
+ 1
? 2
- 6
- 8
+ 6
? 5
5
6 7 8 9 10
10
? 5
- 6
? 4
- 10
+ 5
- 8
+ 3
+ 2
- 3
+ 10
```

### Sample Output #1

```
2 2 1 6 3 8 8 2000001 
9 9 9 7 
1 1
```

## Limit



Time Limit
3.00s

Memory Limit
500.00MB

Tags: binary search, brute force, data structures, implementation
Difficulty: 2200
# Color Rows and Columns

## Problem Description

You have $ n $ rectangles, the $ i $ -th of which has a width of $ a_i $ and a height of $ b_i $ .

You can perform the following operation an unlimited number of times: choose a rectangle and a cell in it, and then color it.

Each time you completely color any row or column, you earn $ 1 $ point. Your task is to score at least $ k $ points with as few operations as possible.

Suppose you have a rectangle with a width of $ 6 $ and a height of $ 3 $ . You can score $ 4 $ points by coloring all the cells in any $ 4 $ columns, thus performing $ 12 $ operations.

## Input Format

The first line contains an integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The following are the descriptions of the test cases.

The first line of each test case description contains two integers $ n $ and $ k $ ( $ 1 \le n \le 1000, 1 \le k \le 100 $ ) — the number of rectangles in the case and the required number of points.

The next $ n $ lines contain the descriptions of the rectangles. The $ i $ -th line contains two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le 100 $ ) — the width and height of the $ i $ -th rectangle.

It is guaranteed that the sum of the values of $ n $ across all test cases does not exceed $ 1000 $ .

## Output Format

For each test case, output a single integer — the minimum number of operations required to score at least $ k $ points. If it is impossible to score at least $ k $ points, output -1.

## Sample #1

### Sample Input #1

```
7
1 4
6 3
1 5
4 4
5 10
1 1
1 1
1 1
1 1
1 1
2 100
1 2
5 6
3 11
2 2
3 3
4 4
3 25
9 2
4 3
8 10
4 18
5 4
8 5
8 3
6 2
```

### Sample Output #1

```
12
14
5
-1
17
80
35
```

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: dp, greedy, implementation, math
Difficulty: 1900