apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
An array $$$a$$$ is called ugly if it contains at least one element which is equal to the sum of all elements before it. If the array is not ugly, it is beautiful.

For example:

- the array $$$[6, 3, 9, 6]$$$ is ugly: the element $$$9$$$ is equal to $$$6 + 3$$$;
- the array $$$[5, 5, 7]$$$ is ugly: the element $$$5$$$ (the second one) is equal to $$$5$$$;
- the array $$$[8, 4, 10, 14]$$$ is beautiful: $$$8 \ne 0$$$, $$$4 \ne 8$$$, $$$10 \ne 8 + 4$$$, $$$14 \ne 8 + 4 + 10$$$, so there is no element which is equal to the sum of all elements before it.

You are given an array $$$a$$$ such that $$$1 \le a_1 \le a_2 \le \dots \le a_n \le 100$$$. You have to reorder the elements of $$$a$$$ in such a way that the resulting array is beautiful. Note that you are not allowed to insert new elements or erase existing ones, you can only change the order of elements of $$$a$$$. You are allowed to keep the array $$$a$$$ unchanged, if it is beautiful.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 100$$$).

## Output Format
For each test case, print the answer as follows:

- if it is impossible to reorder the elements of $$$a$$$ in such a way that it becomes beautiful, print NO;
- otherwise, in the first line, print YES. In the second line, print $$$n$$$ integers — any beautiful array which can be obtained from $$$a$$$ by reordering its elements. If there are multiple such arrays, print any of them.

## Examples
```input
4
4
3 3 6 6
2
10 10
5
1 2 3 4 5
3
1 4 4
```
```output
YES
3 6 3 6
NO
YES
2 4 1 5 3
YES
1 4 4
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ integers.

You have to perform the sequence of $$$n-2$$$ operations on this array:

- during the first operation, you either add $$$a_2$$$ to $$$a_1$$$ and subtract $$$a_2$$$ from $$$a_3$$$, or add $$$a_2$$$ to $$$a_3$$$ and subtract $$$a_2$$$ from $$$a_1$$$;
- during the second operation, you either add $$$a_3$$$ to $$$a_2$$$ and subtract $$$a_3$$$ from $$$a_4$$$, or add $$$a_3$$$ to $$$a_4$$$ and subtract $$$a_3$$$ from $$$a_2$$$;
- ...
- during the last operation, you either add $$$a_{n-1}$$$ to $$$a_{n-2}$$$ and subtract $$$a_{n-1}$$$ from $$$a_n$$$, or add $$$a_{n-1}$$$ to $$$a_n$$$ and subtract $$$a_{n-1}$$$ from $$$a_{n-2}$$$.

So, during the $$$i$$$-th operation, you add the value of $$$a_{i+1}$$$ to one of its neighbors, and subtract it from the other neighbor.

For example, if you have the array $$$[1, 2, 3, 4, 5]$$$, one of the possible sequences of operations is:

- subtract $$$2$$$ from $$$a_3$$$ and add it to $$$a_1$$$, so the array becomes $$$[3, 2, 1, 4, 5]$$$;
- subtract $$$1$$$ from $$$a_2$$$ and add it to $$$a_4$$$, so the array becomes $$$[3, 1, 1, 5, 5]$$$;
- subtract $$$5$$$ from $$$a_3$$$ and add it to $$$a_5$$$, so the array becomes $$$[3, 1, -4, 5, 10]$$$.

So, the resulting array is $$$[3, 1, -4, 5, 10]$$$.

An array is reachable if it can be obtained by performing the aforementioned sequence of operations on $$$a$$$. You have to calculate the number of reachable arrays, and print it modulo $$$998244353$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$3 \le n \le 300$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$).

## Output Format
Print one integer — the number of reachable arrays. Since the answer can be very large, print its remainder modulo $$$998244353$$$.

## Examples
```input
4
1 1 1 1
```
```output
3
```
-----
```input
5
1 2 3 5 0
```
```output
7
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given two permutations $$$a$$$ and $$$b$$$, both of size $$$n$$$. A permutation of size $$$n$$$ is an array of $$$n$$$ elements, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. The elements in each permutation are indexed from $$$1$$$ to $$$n$$$.

You can perform the following operation any number of times:

- choose an integer $$$i$$$ from $$$1$$$ to $$$n$$$;
- let $$$x$$$ be the integer such that $$$a_x = i$$$. Swap $$$a_i$$$ with $$$a_x$$$;
- let $$$y$$$ be the integer such that $$$b_y = i$$$. Swap $$$b_i$$$ with $$$b_y$$$.

Your goal is to make both permutations sorted in ascending order (i. e. the conditions $$$a_1 < a_2 < \dots < a_n$$$ and $$$b_1 < b_2 < \dots < b_n$$$ must be satisfied) using minimum number of operations. Note that both permutations must be sorted after you perform the sequence of operations you have chosen.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$; all $$$a_i$$$ are distinct).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$; all $$$b_i$$$ are distinct).

## Output Format
First, print one integer $$$k$$$ ($$$0 \le k \le 2n$$$) — the minimum number of operations required to sort both permutations. Note that it can be shown that $$$2n$$$ operations are always enough.

Then, print $$$k$$$ integers $$$op_1, op_2, \dots, op_k$$$ ($$$1 \le op_j \le n$$$), where $$$op_j$$$ is the value of $$$i$$$ you choose during the $$$j$$$-th operation.

If there are multiple answers, print any of them.

## Examples
```input
5
1 3 2 4 5
2 1 3 4 5
```
```output
1
2
```
-----
```input
2
1 2
1 2
```
```output
0
```
-----
```input
4
1 3 4 2
4 3 2 1
```
```output
2
3 4
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 6.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a tree of $$$n$$$ vertices and $$$n - 1$$$ edges. The $$$i$$$-th vertex has an initial weight $$$a_i$$$.

Let the distance $$$d_v(u)$$$ from vertex $$$v$$$ to vertex $$$u$$$ be the number of edges on the path from $$$v$$$ to $$$u$$$. Note that $$$d_v(u) = d_u(v)$$$ and $$$d_v(v) = 0$$$.

Let the weighted distance $$$w_v(u)$$$ from $$$v$$$ to $$$u$$$ be $$$w_v(u) = d_v(u) + a_u$$$. Note that $$$w_v(v) = a_v$$$ and $$$w_v(u) \neq w_u(v)$$$ if $$$a_u \neq a_v$$$.

Analogically to usual distance, let's define the eccentricity $$$e(v)$$$ of vertex $$$v$$$ as the greatest weighted distance from $$$v$$$ to any other vertex (including $$$v$$$ itself), or $$$e(v) = \max\limits_{1 \le u \le n}{w_v(u)}$$$.

Finally, let's define the radius $$$r$$$ of the tree as the minimum eccentricity of any vertex, or $$$r = \min\limits_{1 \le v \le n}{e(v)}$$$.

You need to perform $$$m$$$ queries of the following form:

- $$$v_j$$$ $$$x_j$$$ — assign $$$a_{v_j} = x_j$$$.

After performing each query, print the radius $$$r$$$ of the current tree.

## Input Format
The first line contains the single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — the initial weights of vertices.

Next $$$n - 1$$$ lines contain edges of tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — the corresponding edge. The given edges form a tree.

The next line contains the single integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — the number of queries.

Next $$$m$$$ lines contain queries — one query per line. The $$$j$$$-th query contains two integers $$$v_j$$$ and $$$x_j$$$ ($$$1 \le v_j \le n$$$; $$$0 \le x_j \le 10^6$$$) — a vertex and it's new weight.

## Output Format
Print $$$m$$$ integers — the radius $$$r$$$ of the tree after performing each query.

## Examples
```input
6
1 3 3 7 0 1
2 1
1 3
1 4
5 4
4 6
5
4 7
4 0
2 5
5 10
5 5
```
```output
7
4
5
10
7
```

## Note
After the first query, you have the following tree:

The tree after the second query:

After the third query, the radius $$$r = e(2) = 5$$$:

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There is a rectangular maze of size $$$n\times m$$$. Denote $$$(r,c)$$$ as the cell on the $$$r$$$-th row from the top and the $$$c$$$-th column from the left. Two cells are adjacent if they share an edge. A path is a sequence of adjacent empty cells.

Each cell is initially empty. Li Hua can choose some cells (except $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$) and place an obstacle in each of them. He wants to know the minimum number of obstacles needed to be placed so that there isn't a path from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.

Suppose you were Li Hua, please solve this problem.

## Input Format
The first line contains the single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

The first line of each test case contains two integers $$$n,m$$$ ($$$4\le n,m\le 10^9$$$) — the size of the maze.

The second line of each test case contains four integers $$$x_1,y_1,x_2,y_2$$$ ($$$1\le x_1,x_2\le n, 1\le y_1,y_2\le m$$$) — the coordinates of the start and the end.

It is guaranteed that $$$|x_1-x_2|+|y_1-y_2|\ge 2$$$.

## Output Format
For each test case print the minimum number of obstacles you need to put on the field so that there is no path from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.

## Examples
```input
3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6
```
```output
4
2
3
```

## Note
In test case 1, you can put obstacles on $$$(1,3), (2,3), (3,2), (4,2)$$$. Then the path from $$$(2,2)$$$ to $$$(3,3)$$$ will not exist.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Li Hua wants to solve a problem about $$$\varphi$$$ — Euler's totient function. Please recall that $$$\varphi(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1]$$$.$$$^{\dagger,\ddagger}$$$

He has a sequence $$$a_1,a_2,\cdots,a_n$$$ and he wants to perform $$$m$$$ operations:

- "1 $$$l$$$ $$$r$$$" ($$$1\le l\le r\le n$$$) — for each $$$x\in[l,r]$$$, change $$$a_x$$$ into $$$\varphi(a_x)$$$.
- "2 $$$l$$$ $$$r$$$" ($$$1\le l\le r\le n$$$) — find out the minimum changes needed to make sure $$$a_l=a_{l+1}=\cdots=a_r$$$. In each change, he chooses one $$$x\in[l,r]$$$, change $$$a_x$$$ into $$$\varphi(a_x)$$$. Each operation of this type is independent, which means the array doesn't actually change.

Suppose you were Li Hua, please solve this problem.

$$$^\dagger$$$ $$$\gcd(x,y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

$$$^\ddagger$$$ The notation $$$[\textrm{cond}]$$$ equals $$$1$$$ if the condition $$$\textrm{cond}$$$ is true, and $$$0$$$ otherwise.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^{5}$$$) — the number of elements in the array and the number of operations to process, respectively.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},\cdots ,a_{n}$$$ ($$$1\le a_{i}\le 5\cdot 10^{6}$$$) — the elements of the array.

Next $$$m$$$ lines, each line contains three integers $$$t_{i},l_{i},r_{i}$$$ ($$$t_i\in\{1,2\},1\le l_i\le r_i\le n$$$) — the $$$i$$$-th operation.

## Output Format
For each "2 $$$l$$$ $$$r$$$", output the answer in an separate line.

## Examples
```input
5 4
8 1 6 3 7
2 1 5
2 3 4
1 1 3
2 3 4
```
```output
10
2
1
```

## Note
Denote $$$\varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k > 0\end{cases}$$$.

At first, $$$a=[8,1,6,3,7]$$$.

To make sure $$$a_1=a_2=a_3=a_4=a_5$$$, we can change $$$a$$$ to $$$a'=[\varphi^3(8),\varphi^0(1),\varphi^2(6),\varphi^2(3),\varphi^3(7)]=[1,1,1,1,1]$$$, using $$$3+0+2+2+3=10$$$ changes.

To make sure $$$a_3=a_4$$$, we can change $$$a$$$ to $$$a'=[\varphi^0(8),\varphi^0(1),\varphi^1(6),\varphi^1(3),\varphi^0(7)]=[8,1,2,2,7]$$$, using $$$0+0+1+1+0=2$$$ changes.

After "1 $$$1$$$ $$$3$$$", $$$a$$$ is changed to $$$a=[\varphi^1(8),\varphi^1(1),\varphi^1(6),\varphi^0(3),\varphi^0(7)]=[4,1,2,3,7]$$$.

To make sure $$$a_3=a_4$$$, we can change $$$a$$$ to $$$a'=[\varphi^0(4),\varphi^0(1),\varphi^0(2),\varphi^1(3),\varphi^0(7)]=[4,1,2,2,7]$$$, using $$$0+0+0+1+0=1$$$ change.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Li Hua has a tree of $$$n$$$ vertices and $$$n-1$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$.

A pair of vertices $$$(u,v)$$$ ($$$u < v$$$) is considered cute if exactly one of the following two statements is true:

- $$$u$$$ is the vertex with the minimum index among all vertices on the path $$$(u,v)$$$.
- $$$v$$$ is the vertex with the maximum index among all vertices on the path $$$(u,v)$$$.

There will be $$$m$$$ operations. In each operation, he decides an integer $$$k_j$$$, then inserts a vertex numbered $$$n+j$$$ to the tree, connecting with the vertex numbered $$$k_j$$$.

He wants to calculate the number of cute pairs before operations and after each operation.

Suppose you were Li Hua, please solve this problem.

## Input Format
The first line contains the single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of vertices in the tree.

Next $$$n-1$$$ lines contain the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$; $$$u_i\ne v_i$$$) — the corresponding edge. The given edges form a tree.

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

Next $$$m$$$ lines contain operations — one operation per line. The $$$j$$$-th operation contains one integer $$$k_j$$$ ($$$1\le k_j < n+j$$$) — a vertex.

## Output Format
Print $$$m+1$$$ integers — the number of cute pairs before operations and after each operation.

## Examples
```input
7
2 1
1 3
1 4
4 6
4 7
6 5
2
5
6
```
```output
11
15
19
```

## Note
The initial tree is shown in the following picture:

There are $$$11$$$ cute pairs — $$$(1,5),(2,3),(2,4),(2,6),(2,7),(3,4),(3,6),(3,7),(4,5),(5,7),(6,7)$$$.

Similarly, we can count the cute pairs after each operation and the result is $$$15$$$ and $$$19$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You were walking down the street and heard a sound. The sound was described by the string $$$s$$$ consisting of lowercase and uppercase Latin characters. Now you want to find out if the sound was a cat meowing.

For the sound to be a meowing, the string can only contain the letters 'm', 'e', 'o' and 'w', in either uppercase or lowercase. Also:

- string must start with non-empty sequence consisting only of characters 'm' or 'M'
- it must be immediately followed by non-empty sequence consisting only of characters 'e' or 'E'
- it must be immediately followed by non-empty sequence consisting only of characters 'o' or 'O'
- it must be immediately followed by non-empty sequence consisting only of characters 'w' or 'W', this sequence ends the string, after it immediately comes the string end

For example, strings "meow", "mmmEeOWww", "MeOooOw" describe a meowing, but strings "Mweo", "MeO", "moew", "MmEW", "meowmeow" do not.

Determine whether the sound you heard was a cat meowing or something else.

## Input Format
The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 50$$$) — the length of the string describing the sound.

The second line of each test case contains a string $$$s$$$ of $$$n$$$ characters. The string describes the sound you heard and consists only of lowercase and uppercase Latin letters.

## Output Format
For each test case, output on a separate line:

- YES if the sound was a cat meowing;
- NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).

## Examples
```input
7
4
meOw
14
mMmeoOoWWWwwwW
3
mew
7
MmeEeUw
4
MEOW
6
MmyaVW
5
meowA
```
```output
YES
YES
NO
NO
YES
NO
NO
```

## Note
In the first test case, the string consists of a sequence of characters 'm', 'e', 'O', 'w', which satisfies the definition of meowing.

In the second test case, the string consists of a sequence of $$$3$$$ characters 'm' and 'M', one 'e', a sequence of $$$3$$$ characters 'o' and 'O' and a sequence of $$$7$$$ characters 'w' and 'W', which satisfies the definition of meowing.

In the third test case, the string does not describe a meowing because it lacks a sequence of 'o' or 'O' characters between 'e' and 'w'.

In the fourth test case, the string contains the character 'U', so it does not describe a meowing.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is an easy version of the problem. It differs from the hard one only by constraints on $$$n$$$ and $$$t$$$.

There is a deck of $$$n$$$ cards, each of which is characterized by its power. There are two types of cards:

- a hero card, the power of such a card is always equal to $$$0$$$;
- a bonus card, the power of such a card is always positive.

You can do the following with the deck:

- take a card from the top of the deck;
- if this card is a bonus card, you can put it on top of your bonus deck or discard;
- if this card is a hero card, then the power of the top card from your bonus deck is added to his power (if it is not empty), after that the hero is added to your army, and the used bonus discards.

Your task is to use such actions to gather an army with the maximum possible total power.

## Input Format
The first line of input data contains single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the test.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of cards in the deck.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) — card powers in top-down order.

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

## Output Format
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case — the maximum possible total power of the army that can be achieved.

## Examples
```input
5
5
3 3 3 0 0
6
0 3 3 0 0 3
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4
```
```output
6
6
8
9
4
```

## Note
In the first sample, you can take bonuses $$$1$$$ and $$$2$$$. Both hero cards will receive $$$3$$$ power. If you take all the bonuses, one of them will remain unused.

In the second sample, the hero's card on top of the deck cannot be powered up, and the rest can be powered up with $$$2$$$ and $$$3$$$ bonuses and get $$$6$$$ total power.

In the fourth sample, you can take bonuses $$$1$$$, $$$2$$$, $$$3$$$, $$$5$$$ and skip the bonus $$$6$$$, then the hero $$$4$$$ will be enhanced with a bonus $$$3$$$ by $$$5$$$, and the hero $$$7$$$ with a bonus $$$5$$$ by $$$4$$$. $$$4+5=9$$$.

Now solve the problem and return the code.