yl-9/probench huggingface dataset:
# Penacony

## Problem Description

On Penacony, The Land of the Dreams, there exists $ n $ houses and $ n $ roads. There exists a road between house $ i $ and $ i+1 $ for all $ 1 \leq i \leq n-1 $ and a road between house $ n $ and house $ 1 $ . All roads are bidirectional. However, due to the crisis on Penacony, the overseeing family has gone into debt and may not be able to maintain all roads.

There are $ m $ pairs of friendships between the residents of Penacony. If the resident living in house $ a $ is friends with the resident living in house $ b $ , there must be a path between houses $ a $ and $ b $ through maintained roads.

What is the minimum number of roads that must be maintained?

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 10^4 $ ) – the number of test cases.

The first line of each test case contains two integers $ n $ and $ m $ ( $ 3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5 $ ) – the number of houses and the number of friendships.

The next $ m $ lines contain two integers $ a $ and $ b $ ( $ 1 \leq a < b \leq n $ ) – the resident in house $ a $ is friends with the resident in house $ b $ . It is guaranteed all ( $ a, b $ ) are distinct.

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

## Output Format

For each test case, output an integer, the minimum number of roads that must be maintained.

## Sample #1

### Sample Input #1

```
7
8 3
1 8
2 7
4 5
13 4
1 13
2 12
3 11
4 10
10 2
2 3
3 4
10 4
3 8
5 10
2 10
4 10
4 1
1 3
5 2
3 5
1 4
5 2
2 5
1 3
```

### Sample Output #1

```
4
7
2
7
2
3
3
```

## Hint

For the first test case, the following roads must be maintained:

- $ 8 \leftarrow \rightarrow 1 $
- $ 7 \leftarrow \rightarrow 8 $
- $ 1 \leftarrow \rightarrow 2 $
- $ 4 \leftarrow \rightarrow 5 $

## Limit



Time Limit
3.00s

Memory Limit
500.00MB

Tags: brute force, data structures, graphs, greedy, hashing
Difficulty: 2200
# Bomb

## Problem Description

Sparkle gives you two arrays $ a $ and $ b $ of length $ n $ . Initially, your score is $ 0 $ . In one operation, you can choose an integer $ i $ and add $ a_i $ to your score. Then, you must set $ a_i $ = $ \max(0, a_i - b_i) $ .

You only have time to perform $ k $ operations before Sparkle sets off a nuclear bomb! What is the maximum score you can acquire after $ k $ operations?

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases.

The first line of each test case contains $ n $ and $ k $ ( $ 1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9 $ ) — the length of the arrays and the number of operations you can perform.

The following line contains $ n $ integers $ a_1, a_2, ... a_n $ ( $ 1 \leq a_i \leq 10^9 $ ).

The following line contains $ n $ integers $ b_1, b_2, ... b_n $ ( $ 1 \leq b_i \leq 10^9 $ ).

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

## Output Format

For each test case, output an integer, the maximum score you can acquire after $ k $ operations.

## Sample #1

### Sample Input #1

```
5
3 4
5 6 7
2 3 4
5 9
32 52 68 64 14
18 14 53 24 8
5 1000
1 2 3 4 5
5 4 3 2 1
1 1000000
1000000
1
10 6
3 3 5 10 6 8 6 8 7 7
6 1 7 4 1 1 8 9 3 1
```

### Sample Output #1

```
21
349
27
500000500000
47
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, greedy, math
Difficulty: 1900
# Decode

## Problem Description

In a desperate attempt to obtain your waifu favorite character, you have hacked into the source code of the game. After days of struggling, you finally find the binary string that encodes the gacha system of the game. In order to decode it, you must first solve the following problem.

You are given a binary string $ s $ of length $ n $ . For each pair of integers $ (l, r) $ $ (1 \leq l \leq r \leq n) $ , count the number of pairs $ (x, y) $ $ (l \leq x \leq y \leq r) $ such that the amount of $ \mathtt{0} $ equals the amount of $ \mathtt{1} $ in the substring $ s_xs_{x+1}...s_y $ .

Output the sum of counts over all possible $ (l, r) $ modulo $ 10^9+7 $ .

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases.

Each test case contains a binary string $ s $ ( $ 1 \leq |s| \leq 2 \cdot 10^5 $ ). It is guaranteed $ s $ only contains characters $ \mathtt{0} $ and $ \mathtt{1} $ .

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

## Output Format

For each test case, output an integer, the answer modulo $ 10^9+7 $ .

## Sample #1

### Sample Input #1

```
4
0000
01010101
1100111001
11000000111
```

### Sample Output #1

```
0
130
147
70
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: combinatorics, data structures, implementation, math
Difficulty: 1600
# Fun

## Problem Description

Counting is Fun!

— satyam343



Given two integers $ n $ and $ x $ , find the number of triplets ( $ a,b,c $ ) of positive integers such that $ ab + ac + bc \le n $ and $ a + b + c \le x $ .

Note that order matters (e.g. ( $ 1, 1, 2 $ ) and ( $ 1, 2, 1 $ ) are treated as different) and $ a $ , $ b $ , $ c $ must be strictly greater than $ 0 $ .

## Input Format

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

Each test case contains two integers $ n $ and $ x $ ( $ 1 \leq n,x \leq 10^6 $ ).

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ and that the sum of $ x $ over all test cases does not exceed $ 10^6 $ .

## Output Format

Output a single integer — the number of triplets ( $ a,b,c $ ) of positive integers such that $ ab + ac + bc \le n $ and $ a + b + c \le x $ .

## Sample #1

### Sample Input #1

```
4
7 4
10 5
7 1000
900000 400000
```

### Sample Output #1

```
4
10
7
1768016938
```

## Hint

In the first test case, the triplets are ( $ 1, 1, 1 $ ), ( $ 1, 1, 2 $ ), ( $ 1, 2, 1 $ ), and ( $ 2, 1, 1 $ ).

In the second test case, the triplets are ( $ 1, 1, 1 $ ), ( $ 1, 1, 2 $ ), ( $ 1, 1, 3 $ ), ( $ 1, 2, 1 $ ), ( $ 1, 2, 2 $ ), ( $ 1, 3, 1 $ ), ( $ 2, 1, 1 $ ), ( $ 2, 1, 2 $ ), ( $ 2, 2, 1 $ ), and ( $ 3, 1, 1 $ ).

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, brute force, combinatorics, math, number theory
Difficulty: 1500
# Sort

## Problem Description

You are given two strings $ a $ and $ b $ of length $ n $ . Then, you are (forced against your will) to answer $ q $ queries.

For each query, you are given a range bounded by $ l $ and $ r $ . In one operation, you can choose an integer $ i $ ( $ l \leq i \leq r $ ) and set $ a_i = x $ where $ x $ is any character you desire. Output the minimum number of operations you must perform such that $ \texttt{sorted(a[l..r])} = \texttt{sorted(b[l..r])} $ . The operations you perform on one query does not affect other queries.

For an arbitrary string $ c $ , $ \texttt{sorted(c[l..r])} $ denotes the substring consisting of characters $ c_l, c_{l+1}, ... , c_r $ sorted in lexicographical order.

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 1000 $ ) – the number of test cases.

The first line of each test case contains two integers $ n $ and $ q $ ( $ 1 \leq n, q \leq 2 \cdot 10^5 $ ) – the length of both strings and the number of queries.

The following line contains $ a $ of length $ n $ . It is guaranteed $ a $ only contains lowercase latin letters.

The following line contains $ b $ of length $ n $ . It is guaranteed $ b $ only contains lowercase latin letters.

The following $ q $ lines contain two integers $ l $ and $ r $ ( $ 1 \leq l \leq r \leq n $ ) – the range of the query.

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

## Output Format

For each query, output an integer, the minimum number of operations you need to perform in a new line.

## Sample #1

### Sample Input #1

```
3
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4
6 3
uwuwuw
wuwuwu
2 4
1 3
1 6
```

### Sample Output #1

```
0
1
0
2
2
1
1
0
```

## Hint

For the first query, $ \texttt{sorted(a[1..5])} = $ abcde and $ \texttt{sorted(b[1..5])} = $ abcde, so no operations are necessary.

For the second query, you need to set $ a_1 =  $ e. Then, $ \texttt{sorted(a[1..4])} = \texttt{sorted(b[1..4])} =  $ bcde.

## Limit



Time Limit
5.00s

Memory Limit
250.00MB

Tags: dp, greedy, sortings, strings
Difficulty: 1200
# Scale

## Problem Description

Tina has a square grid with $ n $ rows and $ n $ columns. Each cell in the grid is either $ 0 $ or $ 1 $ .

Tina wants to reduce the grid by a factor of $ k $ ( $ k $ is a divisor of $ n $ ). To do this, Tina splits the grid into $ k \times k $ nonoverlapping blocks of cells such that every cell belongs to exactly one block.

Tina then replaces each block of cells with a single cell equal to the value of the cells in the block. It is guaranteed that every cell in the same block has the same value.

For example, the following demonstration shows a grid being reduced by factor of $ 3 $ .

 Original grid  $ 0 $  $ 0 $  $ 0 $  $ 1 $  $ 1 $  $ 1 $  $ 0 $  $ 0 $  $ 0 $  $ 1 $  $ 1 $  $ 1 $  $ 0 $  $ 0 $  $ 0 $  $ 1 $  $ 1 $  $ 1 $  $ 1 $  $ 1 $  $ 1 $  $ 0 $  $ 0 $  $ 0 $  $ 1 $  $ 1 $  $ 1 $  $ 0 $  $ 0 $  $ 0 $  $ 1 $  $ 1 $  $ 1 $  $ 0 $  $ 0 $  $ 0 $   Reduced grid  $ 0 $  $ 1 $  $ 1 $  $ 0 $ Help Tina reduce the grid by a factor of $ k $ .

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 100 $ ) – the number of test cases.

The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \leq n \leq 1000 $ , $ 1 \le k \le n $ ,  $ k $ is a divisor of $ n $ ) — the number of rows and columns of the grid, and the factor that Tina wants to reduce the grid by.

Each of the following $ n $ lines contain $ n $ characters describing the cells of the grid. Each character is either $ 0 $ or $ 1 $ . It is guaranteed every $ k $ by $ k $ block has the same value.

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

## Output Format

For each test case, output the grid reduced by a factor of $ k $ on a new line.

## Sample #1

### Sample Input #1

```
4
4 4
0000
0000
0000
0000
6 3
000111
000111
000111
111000
111000
111000
6 2
001100
001100
111111
111111
110000
110000
8 1
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
```

### Sample Output #1

```
0
01
10
010
111
100
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: greedy, implementation
Difficulty: 800
# Legs

## Problem Description

It's another beautiful day on Farmer John's farm.

After Farmer John arrived at his farm, he counted $ n $ legs. It is known only chickens and cows live on the farm, and a chicken has $ 2 $ legs while a cow has $ 4 $ .

What is the minimum number of animals Farmer John can have on his farm assuming he counted the legs of all animals?

## Input Format

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

Each test case contains an integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^3 $ , $ n $ is even).

## Output Format

For each test case, output an integer, the minimum number of animals Farmer John can have on his farm.

## Sample #1

### Sample Input #1

```
3
2
6
8
```

### Sample Output #1

```
1
2
2
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, math, ternary search
Difficulty: 800
# Let Me Teach You a Lesson (Hard Version)

## Problem Description

This is the hard version of a problem. The only difference between an easy and a hard version is the constraints on $ t $ and $ n $ . You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $ 2 n $ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $ 2 i - 1 $ is sitting at the desk with the knight $ 2 i $ .

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $ i $ -th knight as $ a_i $ . Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $ \max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) $ .

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $ a_i := a_{i + n} $ , $ a_{i + n} := a_i $ for any $ 1 \le i \le n $ . Arthur can make any number of such swaps. What is the best result he can achieve?

## Input Format

Each test consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10\,000 $ ) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100\,000 $ ) — the number of desks.

The second line consists of $ 2n $ integers $ a_1, a_2, \ldots, a_{2 n} $ ( $ 1 \le a_i \le 10^9 $ ) — the intelligence values of the knights.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 100\,000 $ .

## Output Format

For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
0
0
0
2
4
```

## Hint

In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $ 10 $ .

In the third test case, Arthur can make $ 0 $ operations, which will result in the total intelligence of $ 11 $ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $ 2 $ and $ 5 $ and achieve the difference of $ 2 $ . It can be proven that he cannot improve his result any further.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: data structures, dp, matrices, two pointers
Difficulty: 2900
# Let Me Teach You a Lesson (Easy Version)

## Problem Description

This is the easy version of a problem. The only difference between an easy and a hard version is the constraints on $ t $ and $ n $ . You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $ 2 n $ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $ 2 i - 1 $ is sitting at the desk with the knight $ 2 i $ .

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $ i $ -th knight as $ a_i $ . Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $ \max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) $ .

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $ a_i := a_{i + n} $ , $ a_{i + n} := a_i $ for any $ 1 \le i \le n $ . Arthur can make any number of such swaps. What is the best result he can achieve?

## Input Format

Each test consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2000 $ ) — the number of desks.

The second line consists of $ 2n $ integers $ a_1, a_2, \ldots, a_{2 n} $ ( $ 1 \le a_i \le 10^9 $ ) — the intelligence values of the knights.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ .

## Output Format

For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
0
0
0
2
4
```

## Hint

In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $ 10 $ .

In the third test case, Arthur can make $ 0 $ operations, which will result in the total intelligence of $ 11 $ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $ 2 $ and $ 5 $ and achieve the difference of $ 2 $ . It can be proven that he cannot improve his result any further.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: 2-sat, data structures, dp, matrices, two pointers
Difficulty: 2700
# Cases

## Problem Description

You're a linguist studying a mysterious ancient language. You know that

1. Its words consist only of the first $ c $ letters of the Latin alphabet.
2. Each word has a case which can be unambiguously determined by its last letter (different letters correspond to different cases). For example, words "ABACABA" and "ABA" (if they exist) have the same case in this language because they both have the same ending 'A', whereas "ALICE" and "BOB" have different cases. If the language does not have a case corresponding to some letter, it means that the word cannot end with this letter.
3. The length of each word is $ k $ or less.

You have a single text written in this language. Unfortunately, as the language is really ancient, spaces between words are missing and all letters are uppercase. You wonder what is the minimum number of cases the language can have. Can you find this out?

## Input Format

Each test consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10\,000 $ ) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains three integers $ n $ , $ c $ , $ k $ ( $ 1 \le k \le n \le 2^{18} $ , $ 1 \le c \le 18 $ ) — the length of the text, the number of letters in the language, and the maximum length of the word.

The second line contains a string of $ n $ characters — the text itself. Each character is one of the first $ c $ uppercase letters of the Latin alphabet.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2^{18} $ and the sum of $ 2^c $ over all test cases does not exceed $ 2^{18} $ .

## Output Format

For each test case, output a single line consisting of a single integer — the minimum number of cases in the language.

## Sample #1

### Sample Input #1

```
7
5 5 1
ABCDE
3 1 2
AAA
3 2 2
AAB
10 2 2
ABABABABAB
4 4 4
DCBA
1 17 1
Q
9 3 2
ABCABCABC
```

### Sample Output #1

```
5
1
2
1
1
1
2
```

## Hint

In the first test case, there must be five cases in the language (for each of the letters 'A', 'B', 'C', 'D', and 'E' there must be a case that has a corresponding ending).

In the fourth test case, one case with ending 'B' is sufficient.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, brute force, dp, strings
Difficulty: 2300
# Squaring

## Problem Description

ikrpprpp found an array $ a $ consisting of integers. He likes justice, so he wants to make $ a $ fair — that is, make it non-decreasing. To do that, he can perform an act of justice on an index $ 1 \le i \le n $ of the array, which will replace $ a_i $ with $ a_i ^ 2 $ (the element at position $ i $ with its square). For example, if $ a = [2,4,3,3,5,3] $ and ikrpprpp chooses to perform an act of justice on $ i = 4 $ , $ a $ becomes $ [2,4,3,9,5,3] $ .

What is the minimum number of acts of justice needed to make the array non-decreasing?

## Input Format

First line contains an integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. It is followed by the description of test cases.

For each test case, the first line contains an integer $ n $ — size of the array $ a $ . The second line contains $ n $ ( $ 1 \le n \le 2 \cdot 10 ^5 $ ) integers $ a_1, a_2,\ldots, a_n $ ( $ 1 \le a_i \le 10 ^ 6 $ ).

The sum of $ n $ over all test cases does not exceed $ 2 \cdot {10}^5 $ .

## Output Format

For each testcase, print an integer — minimum number of acts of justice required to make the array $ a $ non-decreasing. If it is impossible to do that, print $ -1 $ .

## Sample #1

### Sample Input #1

```
7
3
1 2 3
2
3 2
3
3 1 5
4
1 1 2 3
3
4 3 2
9
16 2 4 2 256 2 4 2 8
11
10010 10009 10008 10007 10006 10005 10004 10003 10002 10001 10000
```

### Sample Output #1

```
0
1
-1
0
3
15
55
```

## Hint

In the first test case, there's no need to perform acts of justice. The array is fair on its own!

In the third test case, it can be proven that the array cannot become non-decreasing.

In the fifth test case, ikrpprppp can perform an act of justice on index 3, then an act of justice on index 2, and finally yet another act of justice on index 3. After that, $ a $ will become $ [4, 9, 16] $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, greedy, implementation, math, number theory
Difficulty: 1800
# Bouquet (Hard Version)

## Problem Description

This is the hard version of the problem. The only difference is that in this version, instead of listing the number of petals for each flower, the number of petals and the quantity of flowers in the store is set for all types of flowers.

A girl is preparing for her birthday and wants to buy the most beautiful bouquet. There are a total of $ n $ different types of flowers in the store, each of which is characterized by the number of petals and the quantity of this type of flower. A flower with $ k $ petals costs $ k $ coins. The girl has decided that the difference in the number of petals between any two flowers she will use to decorate her cake should not exceed one. At the same time, the girl wants to assemble a bouquet with the maximum possible number of petals. Unfortunately, she only has $ m $ coins, and she cannot spend more. What is the maximum total number of petals she can assemble in the bouquet?

## Input Format

Each test consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10\,000 $ ) — the number of test cases. This is followed by descriptions of the test cases.

The first line of each test case contains two integers $ n $ , $ m $ ( $ 1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^{18} $ ) — the number of types of flowers in the store and the number of coins the girl possesses, respectively. The second line of each test case contains $ n $ different integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ), where $ a_i $ is the number of petals of the $ i $ -th flower type in the store (for different indexes $ i \neq j $ , it must be $ a_i \neq a_j $ ). The third line of each test case contains $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 1 \le c_i \le 10^9 $ ), where $ c_i $ is the quantity of the $ i $ -th flower type in the store.

The sum of $ n $ over all test cases does not exceed $ 2 \cdot {10}^5 $ .

## Output Format

For each test case, print one integer — the maximum possible number of petals in a bouquet that a girl can collect, observing all the conditions listed above.

## Sample #1

### Sample Input #1

```
7
3 10
1 2 3
2 2 1
3 1033
206 207 1000
3 4 1
6 20
4 2 7 5 6 1
1 2 1 3 1 7
8 100000
239 30 610 122 24 40 8 2
12 13123 112 1456 124 100 123 10982
6 13
2 4 11 1 3 5
2 2 1 2 2 1
8 10330
206 210 200 201 198 199 222 1000
9 10 11 12 13 14 15 16
2 10000000000
11 12
87312315 753297050
```

### Sample Output #1

```
7
1033
19
99990
13
10000
9999999999
```

## Hint

In the first test case, some valid bouquets are $ (1, 1, 2, 2), (2, 2, 3), (1, 1), (2, 2) $ . The maximum over all valid bouquets not greater than $ 10 $ is $ 7 $ for $ (2, 2, 3) $ . In the second test case, you can assemble a valid bouquet with $ (206, 206, 207, 207, 207) $ with a sum of $ 1033 $ , which is the maximum number of petals the girl can buy. In the third test case, you can assemble a valid bouquet with $ (5, 5, 5, 4) $ with a sum of $ 19 $ . It can be seen that no valid bouquet can have $ 20 $ petals.

## Limit



Time Limit
1.50s

Memory Limit
250.00MB

Tags: binary search, data structures, greedy, math, sortings, two pointers
Difficulty: 1700