You are given a binary string of length $$$n$$$.
You can take two consecutive $$$1$$$s, remove them, and replace them with $$$0$$$.
Also, you can take two consecutive $$$0$$$s, remove them, and replace them with $$$1$$$.
You can do these operations any number of times (possibly zero).
You have to find the lexicographically largest string you can obtain.
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
The first line contains one integer $$$t$$$ $$$( 1 \le t \le 10^4):$$$ the number of test cases.
The first line of each test case contains one integer $$$n$$$ $$$(1 \le n \le 10^5):$$$ the length of the binary string $$$s$$$.
The second line of each test case contains a binary string consisting of $$$n$$$ characters.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\times 10^5$$$
For each test case, output $$$t$$$ : the lexicographically largest string you can obtain.
6600001061010006011000611010114010101010101001410101010110101
1110 110 110 110101 1 110101
Each year, Hogwarts organizes a tournament between different schools to win the Winter Cup. There are $$$N$$$ participating schools. Each school is represented by a champion. Each champion is selected by the Goblet of Fire, a magical object tasked with the selection. The $$$i^{th}$$$ champion has power $$$P_{i}$$$. Dumbledore wants to make this year's edition even more exciting so he introduced two new potions. The first potion increases the power of the wizard by $$$K$$$ while the second potion decreases it by $$$K$$$. Dumbledore will give each wizard at most one potion. He wants to minimize the difference of power between the strongest and the weakest wizard.
Help Dumbledore balance the tournament.
The first line contains an integer $$$T$$$ $$$(1 \le T \le 500)$$$ denoting the number of testcases.
The first line of each testcase in the input contains two integers $$$N$$$ $$$(1 \le N \le 10^3)$$$ and $$$K$$$ $$$(0 \le K \le 10^9).$$$
The second line contains $$$N$$$ integers $$$P_{1},\dots,P_N$$$ $$$(1 \le P_{i} \le 10^{9})$$$ representing the original power of each wizard.
It is guaranteed that the sum of $$$N$$$ across all test cases doesn't exceed $$$5\times 10^{3}$$$
Print the smallest possible difference of power.
35 11 2 3 4 54 21 3 5 94 51 2 3 4
2 4 3
Many of you know Yessine, but very few know that he is a very successful entrepreneur. In fact, he founded his start-up Iceberg Corporation, specialized in cryptocurrency, a few years ago. He is currently a millionaire, but he keeps going to INSAT so he can compete at the ICPC regionals.
As time went on, Yessine's schedule has gotten really busy, so he decided to hire his first employee. He hired his friend Oussama to do the job of a software engineer, a data scientist, and a business analyst while paying him minimal wage. Oussama was very motivated to work, so he didn't care about the money; he just wanted to solve hard problems. One time he was analyzing the evaluation of the cryptocurrency market and came across the following problem:
Given a sequence $$$A$$$ of $$$N$$$ numbers denoting the prices of a certain cryptocurrency over a period of time, find the highest contiguous increase in price (HCI). The HCI is the largest possible difference between the last and first element over all contiguous increasing subsequences.
* A contiguous subsequence $$$A_{i}, A_{i+1},A_{i+2},\dots,A_j$$$ is an increasing sequence if it satisfies $$$A_i \lt A_{i+1} \lt A_{i+2} \lt ... \lt A_j$$$.
Can you solve this problem ?
The first line contains the number of testcases $$$1 \le T\le 100$$$.
The first line of each testcase contains an integer $$$N$$$ ($$$ 1\le N \le10^5 $$$) denoting the length of the sequence.
The second line of each testcase contains $$$N$$$ integers denoting the sequence $$$A$$$ ($$$ 0 \le A_i \le 10^9 $$$).
It is guaranteed that the sum of $$$N$$$ over all testcases doesn't exceed $$$10^{6}$$$.
Print a single integer : the highest contiguous increase of the cryptocurrency.
441 2 3 444 3 2 141 3 2 441 2 2 4
3 0 2 2
As stated in a previous problem, Yessine is a wealthy business man who founded Iceberg Corporation and hired Oussama to work for him. The start-up grew significantly, so he bought a big office and hired one additional employee who can't be anyone other than Rami . The three of them would meet every evening (because none of them would wake up in the morning), and they would work together. Everything was perfect, except for one thing... Sometimes, Rami and Yessine would make Shisha and start smoking in the office. Oussama doesn't really like smoking, so he asked them to stop. They refused at first, but he kept insisting, so they told him they will stop if he wins in a divisibility game.
Oussama and Rami will play on an array $$$A$$$ of $$$n$$$ positive integers, and they agreed on some odd integer $$$k$$$ before starting the game. Oussama and Rami will make alternating moves. But this time, and unlike previous Winter Cups, Oussama insisted on going first. In each turn, the current player will play as follows:
It's guaranteed that the sum of the elements of the array is divisible by $$$k$$$.
Oussama is very good at games, but so is Rami, so both players play optimally. Help Oussama win before his lungs get sick from Shisha.
The first line of the input contains two integers $$$n,k,$$$ with:
"Oussama" if Oussama will win. Otherwise, "Rami" if Rami will win.
3 5 0 2 3
Oussama
3 5 1 1 3
Rami
Harry was in detention when he started to hear a strange voice. He went out and kept following the voice until he found a message written in blood on the wall. The message said "The Chamber of Secrets has been opened, enemies of the heir... beware". There was also a sequence of N integers. Harry looked into the mystery and found out that there is a secret room where a giant Basilisk is living. However, he couldn't understand the written numbers. Fortunately, Moaning Myrtle was passing by. She told him that the sequence of numbers on the wall is a prefix function used to open the door to the chamber. In fact, any sequence of numbers that has the given prefix function will open the door.
The prefix function of an array $$$a$$$ of size $$$n$$$ is a sequence $$$P_{1},P_{2}...P_{n}$$$, where $$$P_{i}$$$ is the maximum value of $$$k$$$ such that $$$k \lt i$$$ and $$$A[1..k] = A[i-k+1..i]$$$ ($$$A[l..r]$$$ denotes a sub-array of an array $$$A$$$ from a position $$$l$$$ to a position $$$r$$$, inclusive). In other words, it's the longest proper prefix of the string $$$A[1..i]$$$ that is equal to its suffix of the same length. Note that the empty array is both a common prefix and suffix of all arrays. Finally, $$$A[i..j]$$$ is the empty array if $$$i \gt j$$$.
For example, for the array $$$A = [1,2,1,3,1,2,1]$$$, the values of the prefix function in positions $$$1,2,...,7$$$ are equal to $$$P=[0,0,1,0,1,2,3]$$$.
Help Harry find a valid sequence of numbers.
Each test contains multiple test cases. The first line contains the number of test cases $$$1 \le T \le 10^4$$$. Description of the test cases follows.
The first line of each test case contains a single number $$$1 \le n \le 10^{5}:$$$ The length of the array $$$P$$$.
The second line of each test case contains $$$n$$$ integers $$$0\le P_{1},P_{2}, \dots, P_{n} \le n$$$.
It is guaranteed that the sum of the values of $$$n$$$ for all test cases does not exceed $$$2\times 10^{5}$$$.
If such an array exists, output $$$n$$$ integers $$$0 \le A_{1},\dots,A_n \le n$$$. Otherwise, output $$$-1$$$.
470 0 1 0 1 2 360 1 0 1 2 160 1 2 3 4 180 1 0 1 2 2 3 0
1 2 1 3 1 2 1 -1 -1 1 1 2 1 1 1 2 3
"Master has given Dobby a tree, Dobby is free"
Harry has opened the Chamber of Secrets and defeated the Basilisk inside using the Sword of Gryffindor. However, he won't rest until he frees his house-elf friend Dobby from his evil master Lucius. To do so, Harry will give Dobby a special gift to free him, a tree! However, he should give him a very specific tree, or else it won't count as a gift. He doesn't know what the tree looks like, but for each node in the tree, he knows the furthest node from it.
A tree, by definition, is a connected graph with $$$n$$$ nodes and $$$n-1$$$ edges. Formally, for each node $$$u\in \{1,\dots,n\}$$$, we know a node $$$v$$$ such that :
$$$$$$\mathrm{dist}(u,v) = \max_{1 \le w \le n}\mathrm{dist}(u,w)$$$$$$
where $$$\mathrm{dist}(u,v)$$$ is the minimum number of edges that have to be traversed to get from $$$u$$$ to $$$v$$$.
Harry wants to know if it is possible for such a tree to exist. Help him free Dobby.
The first line in the input contains one integer $$$n:$$$ the number of vertices in the tree $$$(2 \le n \le 10^{5})$$$
The second line contains $$$n$$$ integers $$$v_{i}:$$$ the furthest node from node $$$i$$$ $$$(1 \le v_{i} \le n)$$$
Print "YES" if Harry can construct the tree and "NO" otherwise.
5 5 2 1 3 2
NO
12 7 1 9 7 11 3 1 9 7 3 3 3
YES
2 2 1
YES
In the second test case, the following tree is a possible construction:
Since getting his job at Iceberg Corporation, Rami has been ignoring his tasks and playing a new game called Grid Crash. It is a game played on a grid $$$G$$$ of size $$$n\times m.$$$ Each cell in the grid is either black, white, or is empty.
Initially, each cell $$$(i,j)$$$ in the grid contains some color $$$c_{i,j}.$$$
Now the game is played as follows:
Now, Rami wants to finish the game in the fewest moves possible. Please help him.
A single integer $$$r:$$$ the minimum number of moves to win the game.
5 5BWBBBWWBWWBWBWBBWBBBWWWWW
3
5 5WWWWWWBBBWWWWWWWBBBWWWWWW
2
5 5WBBBWBWBWBBBWBBBWBWBWBBBW
3
The following example shows a sequence of moves that solves the first game (test case 1) in $$$3$$$ moves. It can be shown that it is optimal:
Since getting his job at Iceberg Corporation, Rami has been ignoring his tasks and playing a new game called Grid Crash. It is a game played on a grid $$$G$$$ of size $$$n\times m.$$$ Each cell in the grid either has some colour, or is empty.
Initially, each cell $$$(i,j)$$$ in the grid contains some color $$$c_{i,j}.$$$ The grid itself contains at most 4 distinct colours.
Now the game is played as follows:
Now, Rami wants to finish the game in the fewest moves possible. Please help him.
A single integer $$$r:$$$ the minimum number of moves to win the game.
5 5 BWBBB WWBWW BWBWB BWBBB WWWWW
3
5 5 RRRRR GGRBB RRRRR ARRRA ARRRA
4
5 5 GGGGG GRRRR GGGGG GRRRR GGGGG
2
It is guaranteed that the grid does not contain more than 4 distinct colours.
The following example shows a sequence of moves that solves the first game (test case 1) in $$$3$$$ moves. It can be shown that it is optimal:
As Iceberg Corporation kept growing and making significant profit, Yessine went from millionaire to billionaire. He got really greedy and decided to hide his money from the government to avoid taxes. To do so, he decided to put all his money in bags and bury them in Sfax. As you may know from previous Winter Cups, Sfax is an $$$N \times M$$$ rectangular grid. Yessine has $$$K$$$ bags of money. He will hide at most one bag per grid cell. However, he won't place them in random cells. Instead, he will bury a bag in a cell if it maximizes the sum of Manhattan distances from all the other cells in Sfax.
Formally, he wants to maximize $$$S$$$ defined as:
$$$$$$S=\sum\limits_{i=1}^N \sum\limits_{j=1}^M \sum\limits_{k=1}^K D(i,j,k)$$$$$$
where $$$D(i,j,k)$$$ denotes the Manhattan distance between cell ($$$i$$$,$$$j$$$) and the $$$k^{th}$$$ piece.
The Manhattan distance between $$$(x,y)$$$ and $$$(x',y')$$$ is $$$\lvert x'-x \rvert + \lvert y'-y \rvert$$$.
Help Yessine hide the money before the government captures him.
The first line contains an integer $$$1 \le T \le 100$$$ denoting the number of testcases.
Each testcase contains three integers $$$N$$$, $$$M$$$, $$$K$$$ such that $$$1 \le N,M,K \le 2\times 10^{4}$$$ and $$$K \le N \times M$$$.
Print a single integer $$$S$$$: the maximum possible sum.
42 2 12 2 23 3 64 4 12
4 8 102 512
It is guaranteed that within the given constraints, for each test case, the result will not exceed $$$10^{18}.$$$
Iceberg Corporation is desired by many working students thanks to its smart ad strategies. Each year, Yessine will get a very large pool of (unpaid) internship applicants. Usually, Yessine will only select beautiful girls without reading any resumes. However, this year, he has heard that companies with diversity and inclusion are more likely to attract investors. So, he decided to include people from different ethnicities.
To select candidates, Yessine has prepared a list of $$$m$$$ minority groups. For each minority, each candidate either belongs or doesn't belong to that minority group.
To maximize diversity, Yessine will select candidates in such a way that no applicant is more diverse than another one. However, if two or more candidates are equally diverse, then Yessine will only select one of them.
A candidate $$$A$$$ is more diverse than $$$B$$$ if the set of minority groups of $$$B$$$ is included in the set of minority groups of $$$A.$$$ Two candidates are equally diverse if they belong to exactly the same minority groups.
Now, 2024 is the year of diversity and inclusion, and Yessine wants to attract more investors. For that reason, he will maximize the number of interns. But still, he will keep in his selection criteria both conditions stated above.
The application pool is very large, and it contains every possible set of minority groups. What is the maximal number of applications Yessine can accept under both criteria. Since the answer can be large, output it modulo $$$M=998'244'353$$$
The input contains one integer $$$1 \le m \le 4\times 10^{3}:$$$ The number of minority groups.
Output one integer, representing the desired answer modulo $$$998'244'353$$$
1
1
2
2
3
3
1936
794915107
2024
109427260
In the second test case, we have two minority groups. Let's say they are $$$\{\text{Asian}, \text{Hispanic}\}.$$$ We have $$$4$$$ possible profiles in total: $$$\{\}, \{\text{Asian}\},\{\text{Hispanic}\}, \{\text{Asian},\text{Hispanic}\}.$$$ Yessine can select at most $$$2$$$ candidates under his criteria, the first belongs to minority groups $$$\{\text{Asian}\},$$$ and the second belongs to minority groups $$$\{\text{Hispanic}\}.$$$ Remember that the existence of candidates belonging to any mix of these minorities is guaranteed.
For the third test case, Let $$$\{\text{Asian},\text{Hispanic},\text{Middle Eastern}\}$$$ be the set of minority groups. Yessine can select $$$3$$$ candidates with the following respective profiles: $$$\{\text{Asian}\},\{\text{Hispanic}\},\{\text{Middle Eastern}\}.$$$ It can be proven that he cannot select more under his criteria.
While at Iceberg Corporation, Oussama worked on a high-frequency cryptocurrency trading system. He tried to implement it using multiple programming languages, but they were all slow. Therefore, he decided to make his own programming language and use it internally in the company. He prepared the specifications and sent them to Rami, who will write a compiler for that. While doing this task, Rami encountered a problem : sometimes, Rami will take some $$$N$$$ elements of different sizes and try to store them in memory. The $$$i$$$th element has size $$$2^{S_i}$$$.
Computer systems are very complicated. You can think of the memory as a block of cells. The cells are numbered 0,1,2,3, and so on (To ease things, you may assume that the memory is infinite). Each cell can store one unit of storage, and the storage starts from position 0. For example, if you were storing 3 pieces of sizes $$${2,4,1}$$$, the first element will occupy cells $$${0,1}$$$, the second will occupy cells $$${2,3,4,5}$$$, while the third will occupy cell 6. The smallest cell occupied by an element is called memory address. In the previous example, the address at which we stored our elements are 0,2,6. Now here is the catch: in reality, computers only store elements of size $$$2^{S_i}$$$ in addresses divisible by $$$2^{S_i}$$$. This is done to make access faster. For example, elements of size 2 can only be stored in addresses $$${0,2,4,6,...}$$$, while elements of size 4 can occupy addresses $$${0,4,8,12,...}$$$. So in the previous example, the placements of the elements isn't valid. What a computer will do in reality is place the element 2 at address 0, leave cells 2 and 3 empty, and place the element of size 4 at address 4, then place element of size 1 at address 8, occupying a total of 9 units of storage. Notice that we wasted 2 units of storage so we can align the element of size 4 with address 4. This problem is called Memory alignment. (You thought this was a programming contest, not a computer architecture course, didn't you?)
While trying to optimize the runtime performance of the new programming language, he wrote an algorithm to optimize the placement of elements in memory. In fact, the algorithm won't take elements in order but will rearrange them in some order to minimize the total space occupied by them. Oussama wanted to test Rami's algorithm, so he asks you to write an algorithm that outputs the minimum possible space occupied by the elements.
The first line contains the number of testcases $$$1 \le T \le 10^3$$$.
The first line of each testcase contains only one integer $$$ 1\le N \le 10^3.$$$
The second line of each testcase contains $$$N$$$ integers $$$ 0 \le S_1, \dots ,S_N \le 20$$$.
Please note that the size of element $$$i$$$ is $$$2^{S_i}$$$.
Print a single integer : the minimum possible memory occupied by the elements.
330 0 031 2 231 2 4
3 10 22
Iceberg Corporation has made many breakthroughs in many areas, such as cryptography and artificial intelligence, where they were able to register many patents.
One of them is a powerful automated personnel identification system that does not suffer from any practical security exploits. It was carefully designed by its prominent engineers: Yessine, Rami, and Oussama. This system identifies each person with his unique disk.
In fact, each disk is composed of $$$n$$$ sectors, where the $$$i^\text{th}$$$ sector is divided into $$$A_i$$$ isometric chunks. Each chunk has its own color from a list of $$$K$$$ available colors.
To have login access, each person will insert his disk into a disk scanner that identifies the person and gives or denies him access. The scanner is smart enough to detect a flipped disk and correctly realign any sector by rotating it.
The security of this system relies heavily on the number of different configurations of disks. Calculate the number of different disk configurations. As the number can be very big, you only have to calculate it modulo $$$M=998244353.$$$
Two configurations are equivalent if you can get one from the other by rotating each sector by any angle and flipping the whole disk around any axis any number of times.
One integer $$$R,$$$ equal to the number of distinct colorings modulo $$$M=998244353$$$
4 33 4 2 1
3834
2 24 2
18
The first test case corresponds to a system designed as follows:
For the second test case, we can enumerate all distinct disks as follows:
This is an interactive problem.
There is a hidden permutation $$$P$$$ of length $$$n$$$ and you have to find it. For this, you have to choose two different integers $$$i$$$ and $$$j$$$, and the jury will give you $$$\text{lcm}(P_{i}, P_{j})$$$.
You can make no more than $$$2n+100$$$ queries in order to guess $$$P$$$.
A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[3,1,2,5,4]$$$ is a permutation, but $$$[1,2,1]$$$ is not a permutation (1 appears twice in the array) and $$$[2,1,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is in the array).
One integer $$$3\le n\le 10^5:$$$ The size of the hidden permutation $$$P$$$. Then, the interaction will start.
After reading the length of the permutation $$$n,$$$ the interaction protocol is as follows :
3 3 6 2
? 1 2 ? 1 3 ? 2 3 ! 3 1 2
After printing a query or the answer, do not forget to output at the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
This is an interactive problem.
There is a hidden permutation $$$P$$$ of length $$$n$$$ and you have to find it. For this, you have to choose two different integers $$$i$$$ and $$$j$$$, and the jury will give you $$$\text{lcm}(P_{i}, P_{j})$$$.
You can make no more than $$$n+100$$$ queries in order to guess $$$P$$$.
A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[3,1,2,5,4]$$$ is a permutation, but $$$[1,2,1]$$$ is not a permutation (1 appears twice in the array) and $$$[2,1,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is in the array).
One integer $$$3\le n\le 10^5:$$$ The size of the hidden permutation $$$P$$$. Then, the interaction will start.
After reading the length of the permutation $$$n,$$$ the interaction protocol is as follows :
3 3 6 2
? 1 2 ? 1 3 ? 2 3 ! 3 1 2
After printing a query or the answer, do not forget to output at the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
In the modular universe, everything is modular, even coordinates!
For example, if someone has coordinates $$$(x,y)$$$ in the normal universe, they will have coordinates $$$(x \bmod n,y\bmod m)$$$ in some modular universe, where $$$(n,m)$$$ is the modularity of that universe.
Now, $$$n\times m$$$ people live in the $$$(n,m)$$$-modular universe. They are usually found at different positions in the universe, but there is always a day called the singularity day, where all the population will gather at the same coordinate $$$(0,0).$$$ This is a very special holiday as only singularity days have this property.
Once the singularity day finishes, for each $$$k\in\{0,\dots,nm-1\},$$$ the $$$k^\text{th}$$$ person will go to the point $$$\left((k \ \text{div} \ m ) \bmod n, k\bmod m\right)$$$ on the next day, and from there on, that person will continue their journey to $$$((2k \ \text{div} \ m) \bmod n, 2k\bmod m),((3k \ \text{div} \ m) \bmod n, 3k\bmod m),\text{etc}\dots$$$ in the subsequent days.
Now, the most important phenomenon in history is the modular big bang, which is the only day in history on which all modular universes have a singularity day at the same moment.
You are from universe $$$(0,0),$$$ where you don't have modular coordinates, and you are asked to inquire more intel about the patterns of universe $$$(n,m).$$$ You will do that by inspecting the number of people residing in the same point $$$(x,y)$$$ during some day $$$d.$$$
Your supervisors shared with you some important intel, which is the day on which the modular big bang occurred.In fact, it is denoted as day $$$0$$$ by your agency's convention. They sent you also $$$Q$$$ queries, where each one is of the form '$$$\mathtt{n\ m\ x\ y\ d}$$$'. For each one of these queries, you have to find the number of people residing in point $$$(x,y)$$$ on day $$$d$$$ in the $$$(n,m)$$$-modular universe. Good luck with that!
For each query, output one integer $$$r$$$ denoting the number of persons residing at position $$$(x,y)$$$ during day $$$d$$$ in the universe $$$(n,m).$$$
51 1 0 0 12 2 0 0 110 20 0 0 3010 20 3 1 1610 20 0 0 5
1 1 100 0 25
In the queries, the time is represented with respect to the modular Big Bang. In fact, day $$$d$$$ means $$$d$$$ days since the Big Bang. In particular, day $$$0$$$ is the day of the modular Big Bang.
Rami got tired of working for a low salary. He asked for a raise, but Yessine told him that the best he can do is buy him a new Shisha. Rami got angry and quit the company. Now he wants to get rich quickly. So, he decided to use the knowledge he acquired at Iceberg Corporation and become a cryptocurrency trader.
In fact, the cryptocurrency market has $$$n$$$ currencies. Also, there are $$$m$$$ pairs of currencies that can be exchanged. For each pair $$$(u,v)$$$, there is a rate $$$r_{u,v}$$$ that represents the exchange rate of the currency $$$u$$$ to the currency $$$v$$$. But that exchange is not free, there is a fee $$$f_{u,v}$$$ that is deducted from the exchanged amount according to the following formula: $$$$$$ \mathrm{amount}(v) = r_{u,v}\times (\mathrm{amount}(u)-f_{u,v}) $$$$$$
Rami is broke, but he can still borrow up to $$$x$$$ amount of money of currency $$$0$$$ from Oussama. He wants to know the minimal integer amount of money he should spend so that he can end up with strictly more money by only converting currencies and make a win.
Rami can exchange currencies as many times as he wants. But, the final amount must be in the currency $$$0$$$.
Formally, let $$$z_1$$$ be the amount that Rami has borrowed from Oussama expressed in currency $$$0$$$, and let $$$z_2$$$ be the amount that he got after the series of conversions, and expressed in currency $$$0$$$ as well. Rami will make a win if and only if $$$\Delta z= z_2-z_1 \gt 0$$$
The first line contains three integers $$$n,m,x,$$$ with $$$1\le n\le 500,$$$ $$$1\le m \le 4000$$$ and $$$0\le x \le 10^9$$$
The next $$$m$$$ lines contain each $$$4$$$ numbers $$$u_i,v_i,r_{u_i,v_i},f_{u_i,v_i}$$$ with:
Output $$$M:$$$ The minimum integer amount he needs to borrow so that he can make a win. If it is impossible to win any amount of money or Rami needs to borrow more than $$$x$$$, output $$$-1$$$
2 2 10001 2 1.01 10.002 1 1.01 10.00
-1
3 4 50001 2 0.70 1.002 1 1.60 1.001 3 0.80 5.003 1 2.00 5.00
23
5 5 10001 2 1.00 1.002 3 1.00 1.003 4 1.00 1.004 1 1.00 1.001 5 10.00 0.00
-1
4 12 10000000001 3 0.61 5.741 2 1.35 8.861 4 0.85 6.002 4 0.61 8.232 3 0.69 9.452 1 0.50 8.713 2 1.46 5.043 4 1.36 8.003 1 0.73 9.894 3 0.85 8.344 2 0.54 5.994 1 1.43 9.60
72