Farmer Nhoj has trapped Bessie in his dungeon! The dungeon consists of $$$N$$$ rooms numbered $$$1$$$ to $$$N$$$, and Bessie must visit them in order from room $$$1$$$ to room $$$N$$$.
To enter room $$$i$$$, Bessie must have at least $$$a_i$$$ keys. After entering room $$$i$$$, she immediately finds and picks up $$$b_i$$$ loose keys. Bessie can carry any number of keys, and keys are not consumed when opening a door.
Before she starts, Bessie may borrow some non-negative integer number of keys from a suspicious dungeon goblin named Kevin. What is the minimum number of keys Bessie needs to borrow in order to visit all $$$N$$$ rooms?
The first line contains an integer $$$N$$$ ($$$1 \le N \le 10^6$$$).
The next $$$N$$$ lines contain two space-separated integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) — the number of keys needed to enter room $$$i$$$ and the number of keys found inside room $$$i$$$.
Output a single non-negative integer: the minimum number of keys Bessie needs to borrow from Kevin.
42 15 33 29 0
4
It can be shown that Bessie must borrow at least $$$4$$$ keys.
- Room $$$1$$$ ($$$a = 2$$$, $$$b = 1$$$): Bessie has $$$4$$$ keys, which meets the requirement. She picks up $$$1$$$ key, now having $$$5$$$.
- Room $$$2$$$ ($$$a = 5$$$, $$$b = 3$$$): Bessie has $$$5$$$ keys, which meets the requirement. She picks up $$$3$$$ keys, now having $$$8$$$.
- Room $$$3$$$ ($$$a = 3$$$, $$$b = 2$$$): Bessie has $$$8$$$ keys. She picks up $$$2$$$ keys, now having $$$10$$$.
- Room $$$4$$$ ($$$a = 9$$$, $$$b = 0$$$): Bessie has $$$10$$$ keys. She picks up $$$0$$$ keys.
Bessie is trying to convert a number $$$X$$$ to $$$Y$$$.
In one operation, Bessie can choose an integer $$$M$$$ ($$$M \ge 1$$$) and round $$$X$$$ to the nearest multiple of $$$M$$$. If $$$X$$$ is exactly in the middle of two multiples of $$$M$$$, it is rounded up. Note that $$$0$$$ is a multiple of every number.
What is the least number of operations Bessie needs to perform to convert $$$X$$$ to $$$Y$$$? Output this number, or $$$-1$$$ if it is impossible.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.
Each of the next $$$T$$$ lines contains two integers $$$X$$$ and $$$Y$$$ ($$$1 \le X, Y \le 10^9$$$) — the initial number and the target number.
For each test case, output a single integer — the minimum number of operations required, or $$$-1$$$ if it is impossible.
52 56 44 13 31 10
22-104
71 1000000000999999999 1999999999 10999999999 11999999999 12999999999 131000000000 100
30-14646464640
In the first testcase of the first sample, $$$X=2$$$ and $$$Y=5$$$. Bessie can perform the following $$$2$$$ operations:
- Choose $$$M=4$$$. The multiples of $$$4$$$ are $$$0, 4, 8, \dots$$$. $$$X=2$$$ is exactly in the middle of $$$0$$$ and $$$4$$$, so it rounds up to $$$4$$$. Now $$$X=4$$$.
- Choose $$$M=5$$$. The multiples of $$$5$$$ are $$$0, 5, 10, \dots$$$. The nearest multiple to $$$4$$$ is $$$5$$$. Now $$$X=5$$$.
It can be proven that it is impossible to do this in fewer than $$$2$$$ operations.
In the second testcase of the first sample, $$$X=6$$$ and $$$Y=4$$$.
- Choose $$$M=5$$$. $$$X=6$$$ is nearest to $$$5$$$. Now $$$X=5$$$.
- Choose $$$M=4$$$. $$$X=5$$$ is nearest to $$$4$$$. Now $$$X=4$$$.
It can be proven that it is impossible to do this in fewer than $$$2$$$ operations.
Bessie is given an array $$$a$$$ of length $$$n$$$ and wants to know whether it's possible to reverse the array by swapping pairs of elements exactly $$$k$$$ times. Can you help her?
Answer $$$q$$$ queries.
The first line contains two space-separated integers $$$n$$$ and $$$q$$$ ($$$2 \le n, q \le 2\cdot10^{5}$$$), the array $$$a$$$'s length and the number of queries, respectively.
The next line contains $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
The next $$$q$$$ lines each contain a positive integer $$$k$$$ ($$$1 \le k \le 10^9$$$).
Output, for each query, YES if exactly $$$k$$$ swaps are sufficient to transform the array into its desired form, and NO otherwise. This is not case-sensitive; for example, Yes, yEs, and yes are all allowed.
4 34 1 2 3234
YES NO YES
6 23 2 2 1 3 423
NO YES
The following information pertains to the first sample input.
For the first query ($$$k = 2$$$), the array can be reversed in $$$2$$$ operations:
| Operation | Array |
| Initial | $$$[4, 1, 2, 3]$$$ |
| Swap $$$a_1$$$ and $$$a_4$$$ | $$$[3, 1, 2, 4]$$$ |
| Swap $$$a_2$$$ and $$$a_3$$$ | $$$[3, 2, 1, 4]$$$ |
For the second query ($$$k = 3$$$), it can be shown that the array cannot be reversed in exactly $$$3$$$ operations.
For the third query ($$$k = 4$$$), the array can be reversed in $$$4$$$ operations:
| Operation | Array |
| Initial | $$$[4, 1, 2, 3]$$$ |
| Swap $$$a_1$$$ and $$$a_2$$$ | $$$[1, 4, 2, 3]$$$ |
| Swap $$$a_2$$$ and $$$a_3$$$ | $$$[1, 2, 4, 3]$$$ |
| Swap $$$a_3$$$ and $$$a_4$$$ | $$$[1, 2, 3, 4]$$$ |
| Swap $$$a_1$$$ and $$$a_3$$$ | $$$[3, 2, 1, 4]$$$ |
Bessie is trapped in an infinite dungeon and must fight a repeating sequence of bosses until she is eventually defeated. Throughout her journey, she has accumulated coins. A line of heroes is willing to fight for her, each for a price.
There are $$$N$$$ bosses, numbered $$$1, 2, \ldots, N$$$. Boss $$$i$$$ has health $$$H_i$$$ and deals $$$D_i$$$ damage. Bessie fights bosses in order. After boss $$$N$$$ is defeated, the sequence starts again from boss $$$1$$$.
There are $$$M$$$ heroes, in a fixed order. Hero $$$j$$$ has health $$$h_j$$$, damage $$$d_j$$$, and cost $$$c_j$$$. Bessie starts with $$$C$$$ coins.
For each hero in order, Bessie may either:
- hire them if she can afford their cost, paying $$$c_j$$$ coins, or
- skip them forever.
If Bessie hires a hero, they immediately fight the current boss. Combat proceeds in rounds:
- The boss attacks first, reducing the hero's health by its damage.
- If the hero is still alive, the hero attacks and deals damage to the boss.
If a hero's health drops to $$$0$$$ or below, they die and are gone forever. If a boss's health drops to $$$0$$$ or below, that boss is defeated and the hero leaves immediately; heroes never continue onto the next boss.
Bessie plays optimally; that is, she make choices that will allow her to deal as much damage as possible.
Note that any excess damage dealt beyond a boss's remaining HP is discarded — overkill does not count nor carry over.
The first line contains three positive integers $$$N$$$, $$$M$$$, and $$$C$$$ ($$$1 \le N \le 10^6$$$, $$$1 \le M \le 5000$$$, $$$0 \le C \le 5000$$$).
The next $$$N$$$ lines contain $$$H_i$$$ and $$$D_i$$$ ($$$1 \le H_i \le 10^9$$$, $$$0 \le D_i \le 10^9$$$).
The next $$$M$$$ lines contain $$$h_j$$$, $$$d_j$$$, and $$$c_j$$$. ($$$1 \le h_j, d_j \le 10^9$$$, $$$0 \le c_j \le 5000$$$).
Print two space-separated integers:
- the damage already dealt to the current boss when Bessie dies
- the total damage dealt to all bosses.
3 5 510 21 08 35 4 33 2 23 9 06 2 21 1 9
0 11
1 3 220 10050 3 0101 7 1101 7 1
14 14
In the first sample, the most optimal strategy is to hire Hero $$$1$$$ for $$$3$$$ coins, dealing $$$8$$$ damage on Boss $$$1$$$. Then, skip Hero $$$2$$$ and hire Hero $$$3$$$ for $$$0$$$ coins, defeating Boss $$$1$$$ (the $$$9$$$ damage is capped to $$$2$$$). Bessie hires Hero $$$4$$$, who then deals $$$1$$$ damage to Boss $$$2$$$ and defeats it. After Hero $$$4$$$ leaves, Bessie is left with Hero $$$5$$$, which is too expensive to hire, thereby forcing us to skip and get defeated. The total damage dealt sums up to $$$11$$$, and no damage is dealt to Boss $$$4$$$.
Another optimal strategy is to hire Hero $$$1$$$, Hero $$$2$$$, and Hero $$$3$$$. We are forced to skip Hero $$$4$$$ and Hero $$$5$$$. This strategy also sums up to $$$11$$$ damage dealt to bosses.
Farmer John has given his favorite cow, Bessie, an array $$$a$$$ of length $$$n$$$!
Bessie first splits the array into $$$n / k$$$ groups each of length $$$k$$$. Then, she performs two types of operations on the array, with all type $$$1$$$ operations coming before all type $$$2$$$ operations.
- Cyclically shift the groups to the left. Formally, if the array was originally $$$a_1, a_2, \ldots, a_n$$$, then after the operation it becomes $$$a_{k + 1}, a_{k + 2}, \ldots, a_n, a_1, \ldots, a_{k}$$$.
- Swap any two adjacent groups. Formally, if the array was originally $$$a_1, a_2, \ldots, a_n$$$, and Bessie decides to swap groups $$$i$$$ and $$$i + 1$$$ ($$$1 \le i \lt n / k$$$), then the array becomes $$$a_1, a_2, \ldots, a_{(i - 1)k}, a_{ik + 1}, \ldots, a_{(i + 1)k}, a_{(i - 1)k + 1}, \ldots, a_{ik}, a_{(i + 1)k + 1}, \ldots, a_n$$$.
Note that you are not allowed to swap group $$$1$$$ and group $$$n / k$$$ as they are not adjacent.
Since Bessie is a very smart cow, she was able to sort the array using the minimum number of operations. Please determine how many operations Bessie used!
In other words, over all valid choices of $$$k$$$ and all valid sequences of operations with type $$$1$$$ operations coming before type $$$2$$$ operations, what is the minimum number of operations to sort the array? It can be shown that this is always possible.
Each test consists of multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, ..., a_n$$$ $$$(0 \le a_i \le 10^9)$$$
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the minimum number of operations required to sort the array $$$a$$$.
463 4 1 2 5 682 2 2 2 1 1 2 251 5 2 3 555 1 2 4 3
1122
In the first test case, it's optimal to choose $$$k = 2$$$, then perform the second operation with the first and second groups.
In the second test case, it's optimal to choose $$$k = 2$$$, then perform the second operation with the third and fourth groups.
In the third test case, it's optimal to choose $$$k = 1$$$ and apply the second operation twice:
| Operation | Array |
| Initial | $$$[1, 5, 2, 3, 5]$$$ |
| Swap groups $$$2$$$ and $$$3$$$ | $$$[1, 2, 5, 3, 5]$$$ |
| Swap groups $$$3$$$ and $$$4$$$ | $$$[1, 2, 3, 5, 5]$$$ |
In the fourth test case, it's optimal to choose $$$k = 1$$$ and apply one type $$$1$$$ operation followed by one type $$$2$$$ operation:
| Operation | Array |
| Initial | $$$[5, 1, 2, 4, 3]$$$ |
| Cyclic shift to the left | $$$[1, 2, 4, 3, 5]$$$ |
| Swap groups $$$3$$$ and $$$4$$$ | $$$[1, 2, 3, 4, 5]$$$ |
Note that swapping before shifting would have been invalid, because all type $$$1$$$ operations must come before all type $$$2$$$ operations.
Bessie recently got a job working at Cowpital One, the largest cow-run bank in the country! She was having a perfectly fine day not worrying about algorithmic problems until one of her clients keeps making mistakes when giving her a security code that consists of $$$N$$$ numbers $$$a_1, a_2, \ldots, a_N$$$, which really annoys her.
The client will make $$$Q$$$ corrections to her previous codes, one at each time $$$t = 1, 2, \ldots, Q$$$ (time $$$0$$$ is the original code). The $$$i$$$-th correction (at time $$$i$$$) consists of:
- Referring to a previous time $$$t_i$$$ ($$$0 \le t_i \lt i$$$).
- Updating the code at time $$$t_i$$$ by replacing the $$$u_i$$$-th number with a new number $$$x_i$$$.
In other words, the code at time $$$i$$$ is equal to the code at time $$$t_i$$$ ($$$0 \le t_i \lt i$$$) with up to one value changed.
Since Bessie is so annoyed, she tries to calm herself down by thinking of her $$$D$$$ favorite numbers $$$d_1, d_2, \ldots, d_D$$$. It is guaranteed that all $$$d_i$$$ are distinct. After each correction (and for the original code), Bessie wants to compute the sum of all favorite numbers $$$d_k$$$ that divide every number $$$a_j$$$ in the current security code.
Help Bessie calm herself down!
The first line contains three integers $$$N$$$, $$$Q$$$, and $$$D$$$ ($$$1 \le N \le 2 \cdot 10^5$$$, $$$1 \le Q \le 2 \cdot 10^5$$$, $$$1 \le D \le 30$$$).
The second line contains $$$D$$$ distinct integers $$$d_1, d_2, \ldots, d_D$$$ ($$$2 \le d_i \le 10^{18}$$$) — Bessie's favorite numbers.
The third line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_j \le 10^{18}$$$) — the initial security code.
The next $$$Q$$$ lines each contain three integers $$$t_i$$$, $$$u_i$$$, and $$$x_i$$$ ($$$0 \le t_i \lt i$$$, $$$1 \le u_i \le N$$$, $$$1 \le x_i \le 10^{18}$$$) — the time to base the correction on, the index to update, and the new value.
Print $$$Q + 1$$$ integers, one per line. The $$$i$$$-th integer (0-indexed) should be the sum of all favorite numbers that divide every number in the security code at time $$$i$$$.
3 3 32 3 510 15 200 2 301 1 61 1 7
5 7 2 0
Bessie's favorite numbers are $$$2$$$, $$$3$$$, and $$$5$$$.
- Time 0: The original code is $$$[10, 15, 20]$$$. Only $$$5$$$ divides all numbers, so the sum $$$= 5$$$.
- Time 1: Based on time $$$0$$$, the second number becomes $$$30$$$, giving $$$[10, 30, 20]$$$. Both $$$5$$$ and $$$2$$$ divide all numbers, so the sum $$$= 5 + 2 = 7$$$.
- Time 2: Based on time $$$1$$$, the first number becomes $$$6$$$, giving $$$[6, 30, 20]$$$. Only $$$2$$$ divides all numbers, so the sum $$$= 2$$$.
- Time 3: Based on time $$$1$$$, the first number becomes $$$7$$$, giving $$$[7, 30, 20]$$$. None of Bessie's favorite numbers divide every number, so the sum $$$= 0$$$.
For an $$$n$$$-digit base-$$$10$$$ integer with leading zeros, define the Kaprekar mapping $$$K_n(x)$$$ as follows:
- Let $$$a$$$ be the integer obtained by sorting the digits of $$$x$$$ in non-decreasing order.
- Let $$$b$$$ be the integer obtained by sorting the digits of $$$x$$$ in non-increasing order.
- Then $$$K_n(x) = b - a$$$.
For example, if $$$n = 4$$$ and $$$x = 2103$$$, then its digits are $$$0,1,2,3$$$. Sorting them gives $$$a = 0123 = 123$$$ and $$$b = 3210$$$, so $$$K_4(2103) = 3210 - 123 = 3087$$$.
The Kaprekar set of $$$x$$$, denoted $$$S_n(x)$$$, is defined as follows:
- $$$x$$$ is in $$$S_n(x)$$$.
- If $$$a$$$ is in $$$S_n(x)$$$, then $$$K_n(a)$$$ is also in $$$S_n(x)$$$.
You are given $$$q$$$ queries. For each query value $$$y_i$$$, determine the number of integers $$$x$$$ such that $$$0 \le x \le 10^n - 1$$$ and $$$y_i \in S_n(x)$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n \le 12,\; 1 \le q \le 10^5)$$$.
The second line contains $$$q$$$ integers $$$y_1, y_2, \dots, y_q$$$ $$$(0 \le y_i \le 10^n - 1)$$$.
Print $$$q$$$ lines containing the answers to the queries in order.
2 50 9 18 54 98
10 90 17 9 1
3 60 495 594 999 321 100
10 990 841 1 1 1
In the first query of the first test, there are exactly $$$10$$$ values of $$$x$$$ whose Kaprekar set contains $$$0$$$, namely $$$$$$ 00, 11, 22, \dots, 99. $$$$$$
In the fourth query of the first test, there are exactly $$$9$$$ values of $$$x$$$ whose Kaprekar set contains $$$54$$$, namely $$$$$$ 6, 17, 28, 39, 54, 60, 71, 82, 93. $$$$$$
In the fifth query of the first test, $$$98$$$ is the only number which contains $$$98$$$ in its Kaprekar set.
For two positive integers $$$l, r$$$, $$$f(l, r)$$$ is defined as the number of ordered pairs $$$(a, b)$$$ such that $$$l \le a + b \le r$$$, $$$a$$$ and $$$b$$$ are positive, and $$$\text{gcd}(a, b) = p$$$, where $$$p$$$ is a prime number.
There will be $$$q$$$ queries of the form $$$l, r$$$. For each query, output $$$f(l, r)$$$.
The first line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$). Then $$$q$$$ lines follow, each containing two integers $$$l, r$$$ ($$$2 \le l \le r \le 2 \cdot 10^5$$$).
Print $$$q$$$ lines, each containing one integer, $$$f(l, r)$$$.
210 1153 67670
5 629501299
In the first query, the ordered pairs would be $$$(2, 8), (8, 2), (4, 6), (6, 4), (5, 5)$$$.
Bessie has an array $$$a$$$ of length $$$n$$$ and a list of $$$m$$$ intervals $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$.
In one operation, Bessie can choose one of the $$$m$$$ given intervals $$$[l_i, r_i]$$$ and a non-negative integer $$$x$$$, and XOR all elements $$$a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}$$$ with $$$x$$$.
She may use each interval any number of times (possibly zero), with possibly different values of $$$x$$$ each time. Determine whether it is possible to make all elements of $$$a$$$ equal to zero using at most $$$m$$$ operations. If it is possible, construct such a sequence of operations. Note that Bessie doesn't need to minimize the number of operations.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le m \le 200\,000$$$) — the length of the array and the number of intervals.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — the elements of the array.
Each of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the endpoints of the $$$i$$$-th interval.
If it is impossible, print $$$-1$$$.
Otherwise, print an integer $$$k$$$ ($$$0 \le k \le m$$$) — the number of operations. Then print $$$k$$$ lines. The $$$j$$$-th of these lines should contain two integers $$$i_j$$$ and $$$x_j$$$ ($$$1 \le i_j \le m$$$, $$$0 \le x_j \le 10^9$$$) — meaning that in the $$$j$$$-th operation, the interval $$$[l_{i_j}, r_{i_j}]$$$ is XORed with $$$x_j$$$.
If there are multiple valid solutions, print any of them.
3 33 1 21 32 31 2
2 2 2 3 3
3 21 2 31 13 3
-1
In the first example, one valid solution uses $$$2$$$ operations:
- Use interval $$$2$$$ ($$$[2, 3]$$$) with $$$x = 2$$$: $$$[3, 1 \oplus 2, 2 \oplus 2] = [3, 3, 0]$$$.
- Use interval $$$3$$$ ($$$[1, 2]$$$) with $$$x = 3$$$: $$$[3 \oplus 3, 3 \oplus 3, 0] = [0, 0, 0]$$$.
In the second example, it is impossible to make all elements zero.
Bessie and Elsie are exchanging Christmas gifts. Elsie gifts Bessie an array $$$A$$$ of length $$$N$$$. However, Bessie forgot to get a gift for Elsie, so she came up with a devious plan: Bessie will create a gift for Elsie based on Elsie's gift!
A subarray $$$A_i, A_{i + 1}, \ldots, A_j$$$ of length $$$L = j-i+1$$$ is called special if none of the elements divides its length. Formally, it is special if for every $$$k$$$ with $$$i \le k \le j$$$ we have $$$$$$L \bmod A_k \ne 0.$$$$$$
Bessie's gift array $$$F$$$ is defined as follows: for each index $$$i$$$, the value $$$F[i]$$$ is the number of special subarrays in $$$A$$$ that start at index $$$i$$$.
Help Bessie compute the array $$$F$$$.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 200000$$$) — the number of test cases.
Each test case begins with a line containing a single integer $$$N$$$ ($$$1 \leq N \leq 200000$$$) — the number of elements in the array $$$A$$$.
The second line of each test case contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_n$$$ ($$$1 \leq A_i \leq N$$$).
The sum of $$$N$$$ over all test cases does not exceed $$$200000$$$.
For each test case, print $$$N$$$ integers on a single line.
232 3 251 5 4 3 2
1 1 10 2 2 1 1
Bessie has her eyes set on the greatest heist of the century: The Great Polygonal Diamond. However, the diamond is encased inside a large reflective prism. The prism is a regular polygon with $$$n$$$ sides, where side $$$i$$$ has an integer stability $$$a_i$$$. Due to poor engineering, some sides may have negative stability.
To escape with the diamond, Bessie must destroy the surrounding prism by shooting precise laser beams into it. A shot works as follows:
- She chooses a nonnegative integer energy $$$e$$$.
- She chooses two distinct sides of the prism: one (unshattered) side to drill into $$$s$$$ and one (possibly shattered) side to aim at $$$t$$$. She always drills into and aims at the midpoints of those sides.
- After being fired, the laser beam travels in a straight line, bouncing off the prism's interior edges. The beam starts at $$$s$$$, moves to $$$t$$$, and then continues to bounce based on the Law of Reflection.
- Every side the beam makes contact with, including the side originally drilled into, shatters immediately after impact.
- The beam stops once the laser has shattered $$$e$$$ sides, or the laser reaches a side that is already shattered. Values of $$$e$$$ larger than the minimum energy required to reach a shattered side have no effect.
For example, when $$$n = 8$$$, two valid shots (using different lasers) could be: $$$s = 1$$$, $$$t = 4$$$, $$$e = 5$$$ (left) or $$$s = 2, t = 8, e = 9$$$ (right). These shots would shatter sides labeled $$$(1, 2, 4, 5, 7)$$$ and $$$(2, 4, 6, 8)$$$ respectively. Note that the laser stops after shattering $$$e = 5$$$ sides in the example on the left (the initially chosen side $$$s$$$ counts). In the example on the right, the laser stops after shattering $$$4 \lt e$$$ sides because it reaches a side that is already shattered, namely side $$$2$$$.
To have the best chance of breaking in, Bessie wants to create the most unstable structure using at most $$$m$$$ shots. She can only afford one specialized model of laser, so all shots must have the same angle of reflection with the original drilled side (in either direction). Sides that are previously shattered remain shattered. Shots are performed one after another in an order chosen by Bessie.
Output the maximum total stability of all sides Bessie manages to shatter.
The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 300$$$).
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 1000$$$, $$$1 \le m \le 50$$$) — the number of sides and the maximum number of shots.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the stability values of the sides.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$1000$$$.
For each test case, print a single integer: the maximum total stability of all sides Bessie manages to shatter.
37 15 -2 8 1 -7 -9 -18 11 2 -3 4 5 -6 7 -818 2-53 63 16 19 -84 28 64 18 -17 23 40 76 27 68 54 30 94 22
1319642
The first case can be achieved by selecting $$$s = 1$$$, $$$t = 3$$$, $$$e = 2$$$. It can be proven no other single shot can do better than this.
The second case can be achieved by selecting $$$s = 1$$$, $$$t = 4$$$, $$$e = 5$$$ (as shown in the image).
The third case can be achieved by selecting $$$s = 4$$$, $$$t=8$$$, $$$e = 999$$$ and $$$s = 15$$$, $$$t = 11$$$, $$$e=6$$$ for the first and second shots respectively.