A new delivery of clothing has arrived today to the clothing store. This delivery consists of $$$a$$$ ties, $$$b$$$ scarves, $$$c$$$ vests and $$$d$$$ jackets.
The store does not sell single clothing items — instead, it sells suits of two types:
- a suit of the first type consists of one tie and one jacket;
- a suit of the second type consists of one scarf, one vest and one jacket.
Each suit of the first type costs $$$e$$$ coins, and each suit of the second type costs $$$f$$$ coins.
Calculate the maximum possible cost of a set of suits that can be composed from the delivered clothing items. Note that one item cannot be used in more than one suit (though some items may be left unused).
The first line contains one integer $$$a$$$ $$$(1 \le a \le 100\,000)$$$ — the number of ties.
The second line contains one integer $$$b$$$ $$$(1 \le b \le 100\,000)$$$ — the number of scarves.
The third line contains one integer $$$c$$$ $$$(1 \le c \le 100\,000)$$$ — the number of vests.
The fourth line contains one integer $$$d$$$ $$$(1 \le d \le 100\,000)$$$ — the number of jackets.
The fifth line contains one integer $$$e$$$ $$$(1 \le e \le 1\,000)$$$ — the cost of one suit of the first type.
The sixth line contains one integer $$$f$$$ $$$(1 \le f \le 1\,000)$$$ — the cost of one suit of the second type.
Print one integer — the maximum total cost of some set of suits that can be composed from the delivered items.
4 5 6 3 1 2
6
12 11 13 20 4 6
102
17 14 5 21 15 17
325
It is possible to compose three suits of the second type in the first example, and their total cost will be $$$6$$$. Since all jackets will be used, it's impossible to add anything to this set.
The best course of action in the second example is to compose nine suits of the first type and eleven suits of the second type. The total cost is $$$9 \cdot 4 + 11 \cdot 6 = 102$$$.
There are $$$n$$$ blocks arranged in a row and numbered from left to right, starting from one. Each block is either black or white.
You may perform the following operation zero or more times: choose two adjacent blocks and invert their colors (white block becomes black, and vice versa).
You want to find a sequence of operations, such that they make all the blocks having the same color. You don't have to minimize the number of operations, but it should not exceed $$$3 \cdot n$$$. If it is impossible to find such a sequence of operations, you need to report it.
The first line contains one integer $$$n$$$ ($$$2 \le n \le 200$$$) — the number of blocks.
The second line contains one string $$$s$$$ consisting of $$$n$$$ characters, each character is either "W" or "B". If the $$$i$$$-th character is "W", then the $$$i$$$-th block is white. If the $$$i$$$-th character is "B", then the $$$i$$$-th block is black.
If it is impossible to make all the blocks having the same color, print $$$-1$$$.
Otherwise, print an integer $$$k$$$ ($$$0 \le k \le 3 \cdot n$$$) — the number of operations. Then print $$$k$$$ integers $$$p_1, p_2, \dots, p_k$$$ $$$(1 \le p_j \le n - 1)$$$, where $$$p_j$$$ is the position of the left block in the pair of blocks that should be affected by the $$$j$$$-th operation.
If there are multiple answers, print any of them.
8 BWWWWWWB
3 6 2 4
4 BWBB
-1
5 WWWWW
0
3 BWB
2 2 1
In the first example, it is possible to make all blocks black in $$$3$$$ operations. Start with changing blocks $$$6$$$ and $$$7$$$, so the sequence is "BWWWWBBB". Then change blocks $$$2$$$ and $$$3$$$, so the sequence is "BBBWWBB". And finally, change blocks $$$4$$$ and $$$5$$$, so all blocks are black.
It is impossible to make all colors equal in the second example.
All blocks are already white in the third example.
In the fourth example it is possible to make all blocks white in two operations: first operation is to change blocks $$$2$$$ and $$$3$$$ (so the sequence is "BBW"), and then change blocks $$$1$$$ and $$$2$$$ (so all blocks are white).
The map of the capital of Berland can be viewed on the infinite coordinate plane. Each point with integer coordinates contains a building, and there are streets connecting every building to four neighbouring buildings. All streets are parallel to the coordinate axes.
The main school of the capital is located in $$$(s_x, s_y)$$$. There are $$$n$$$ students attending this school, the $$$i$$$-th of them lives in the house located in $$$(x_i, y_i)$$$. It is possible that some students live in the same house, but no student lives in $$$(s_x, s_y)$$$.
After classes end, each student walks from the school to his house along one of the shortest paths. So the distance the $$$i$$$-th student goes from the school to his house is $$$|s_x - x_i| + |s_y - y_i|$$$.
The Provision Department of Berland has decided to open a shawarma tent somewhere in the capital (at some point with integer coordinates). It is considered that the $$$i$$$-th student will buy a shawarma if at least one of the shortest paths from the school to the $$$i$$$-th student's house goes through the point where the shawarma tent is located. It is forbidden to place the shawarma tent at the point where the school is located, but the coordinates of the shawarma tent may coincide with the coordinates of the house of some student (or even multiple students).
You want to find the maximum possible number of students buying shawarma and the optimal location for the tent itself.
The first line contains three integers $$$n$$$, $$$s_x$$$, $$$s_y$$$ ($$$1 \le n \le 200\,000$$$, $$$0 \le s_x, s_y \le 10^{9}$$$) — the number of students and the coordinates of the school, respectively.
Then $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$x_i$$$, $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^{9}$$$) — the location of the house where the $$$i$$$-th student lives. Some locations of houses may coincide, but no student lives in the same location where the school is situated.
The output should consist of two lines. The first of them should contain one integer $$$c$$$ — the maximum number of students that will buy shawarmas at the tent.
The second line should contain two integers $$$p_x$$$ and $$$p_y$$$ — the coordinates where the tent should be located. If there are multiple answers, print any of them. Note that each of $$$p_x$$$ and $$$p_y$$$ should be not less than $$$0$$$ and not greater than $$$10^{9}$$$.
4 3 2 1 3 4 2 5 1 4 1
3 4 2
3 100 100 0 0 0 0 100 200
2 99 100
7 10 12 5 6 20 23 15 4 16 5 4 54 12 1 4 15
4 10 11
In the first example, If we build the shawarma tent in $$$(4, 2)$$$, then the students living in $$$(4, 2)$$$, $$$(4, 1)$$$ and $$$(5, 1)$$$ will visit it.
In the second example, it is possible to build the shawarma tent in $$$(1, 1)$$$, then both students living in $$$(0, 0)$$$ will visit it.
You play a strategic video game (yeah, we ran out of good problem legends). In this game you control a large army, and your goal is to conquer $$$n$$$ castles of your opponent.
Let's describe the game process in detail. Initially you control an army of $$$k$$$ warriors. Your enemy controls $$$n$$$ castles; to conquer the $$$i$$$-th castle, you need at least $$$a_i$$$ warriors (you are so good at this game that you don't lose any warriors while taking over a castle, so your army stays the same after the fight). After you take control over a castle, you recruit new warriors into your army — formally, after you capture the $$$i$$$-th castle, $$$b_i$$$ warriors join your army. Furthermore, after capturing a castle (or later) you can defend it: if you leave at least one warrior in a castle, this castle is considered defended. Each castle has an importance parameter $$$c_i$$$, and your total score is the sum of importance values over all defended castles. There are two ways to defend a castle:
- if you are currently in the castle $$$i$$$, you may leave one warrior to defend castle $$$i$$$;
- there are $$$m$$$ one-way portals connecting the castles. Each portal is characterised by two numbers of castles $$$u$$$ and $$$v$$$ (for each portal holds $$$u \gt v$$$). A portal can be used as follows: if you are currently in the castle $$$u$$$, you may send one warrior to defend castle $$$v$$$.
Obviously, when you order your warrior to defend some castle, he leaves your army.
You capture the castles in fixed order: you have to capture the first one, then the second one, and so on. After you capture the castle $$$i$$$ (but only before capturing castle $$$i + 1$$$) you may recruit new warriors from castle $$$i$$$, leave a warrior to defend castle $$$i$$$, and use any number of portals leading from castle $$$i$$$ to other castles having smaller numbers. As soon as you capture the next castle, these actions for castle $$$i$$$ won't be available to you.
If, during some moment in the game, you don't have enough warriors to capture the next castle, you lose. Your goal is to maximize the sum of importance values over all defended castles (note that you may hire new warriors in the last castle, defend it and use portals leading from it even after you capture it — your score will be calculated afterwards).
Can you determine an optimal strategy of capturing and defending the castles?
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 5000$$$, $$$0 \le m \le \min(\frac{n(n - 1)}{2}, 3 \cdot 10^5)$$$, $$$0 \le k \le 5000$$$) — the number of castles, the number of portals and initial size of your army, respectively.
Then $$$n$$$ lines follow. The $$$i$$$-th line describes the $$$i$$$-th castle with three integers $$$a_i$$$, $$$b_i$$$ and $$$c_i$$$ ($$$0 \le a_i, b_i, c_i \le 5000$$$) — the number of warriors required to capture the $$$i$$$-th castle, the number of warriors available for hire in this castle and its importance value.
Then $$$m$$$ lines follow. The $$$i$$$-th line describes the $$$i$$$-th portal with two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le v_i \lt u_i \le n$$$), meaning that the portal leads from the castle $$$u_i$$$ to the castle $$$v_i$$$. There are no two same portals listed.
It is guaranteed that the size of your army won't exceed $$$5000$$$ under any circumstances (i. e. $$$k + \sum\limits_{i = 1}^{n} b_i \le 5000$$$).
If it's impossible to capture all the castles, print one integer $$$-1$$$.
Otherwise, print one integer equal to the maximum sum of importance values of defended castles.
4 3 7 7 4 17 3 0 8 11 2 0 13 3 5 3 1 2 1 4 3
5
4 3 7 7 4 17 3 0 8 11 2 0 13 3 5 3 1 2 1 4 1
22
4 3 7 7 4 17 3 0 8 11 2 0 14 3 5 3 1 2 1 4 3
-1
The best course of action in the first example is as follows:
- capture the first castle;
- hire warriors from the first castle, your army has $$$11$$$ warriors now;
- capture the second castle;
- capture the third castle;
- hire warriors from the third castle, your army has $$$13$$$ warriors now;
- capture the fourth castle;
- leave one warrior to protect the fourth castle, your army has $$$12$$$ warriors now.
This course of action (and several other ones) gives $$$5$$$ as your total score.
The best course of action in the second example is as follows:
- capture the first castle;
- hire warriors from the first castle, your army has $$$11$$$ warriors now;
- capture the second castle;
- capture the third castle;
- hire warriors from the third castle, your army has $$$13$$$ warriors now;
- capture the fourth castle;
- leave one warrior to protect the fourth castle, your army has $$$12$$$ warriors now;
- send one warrior to protect the first castle through the third portal, your army has $$$11$$$ warriors now.
This course of action (and several other ones) gives $$$22$$$ as your total score.
In the third example it's impossible to capture the last castle: you need $$$14$$$ warriors to do so, but you can accumulate no more than $$$13$$$ without capturing it.
At first, let's define function $$$f(x)$$$ as follows: $$$$$$ \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix} $$$$$$
We can see that if we choose some value $$$v$$$ and will apply function $$$f$$$ to it, then apply $$$f$$$ to $$$f(v)$$$, and so on, we'll eventually get $$$1$$$. Let's write down all values we get in this process in a list and denote this list as $$$path(v)$$$. For example, $$$path(1) = [1]$$$, $$$path(15) = [15, 14, 7, 6, 3, 2, 1]$$$, $$$path(32) = [32, 16, 8, 4, 2, 1]$$$.
Let's write all lists $$$path(x)$$$ for every $$$x$$$ from $$$1$$$ to $$$n$$$. The question is next: what is the maximum value $$$y$$$ such that $$$y$$$ is contained in at least $$$k$$$ different lists $$$path(x)$$$?
Formally speaking, you need to find maximum $$$y$$$ such that $$$\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k$$$.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$).
Print the only integer — the maximum value that is contained in at least $$$k$$$ paths.
11 3
5
11 6
4
20 20
1
14 5
6
1000000 100
31248
In the first example, the answer is $$$5$$$, since $$$5$$$ occurs in $$$path(5)$$$, $$$path(10)$$$ and $$$path(11)$$$.
In the second example, the answer is $$$4$$$, since $$$4$$$ occurs in $$$path(4)$$$, $$$path(5)$$$, $$$path(8)$$$, $$$path(9)$$$, $$$path(10)$$$ and $$$path(11)$$$.
In the third example $$$n = k$$$, so the answer is $$$1$$$, since $$$1$$$ is the only number occuring in all paths for integers from $$$1$$$ to $$$20$$$.
Recently a lot of students were enrolled in Berland State University. All students were divided into groups according to their education program. Some groups turned out to be too large to attend lessons in the same auditorium, so these groups should be divided into two subgroups. Your task is to help divide the first-year students of the computer science faculty.
There are $$$t$$$ new groups belonging to this faculty. Students have to attend classes on three different subjects — maths, programming and P. E. All classes are held in different places according to the subject — maths classes are held in auditoriums, programming classes are held in computer labs, and P. E. classes are held in gyms.
Each group should be divided into two subgroups so that there is enough space in every auditorium, lab or gym for all students of the subgroup. For the first subgroup of the $$$i$$$-th group, maths classes are held in an auditorium with capacity of $$$a_{i, 1}$$$ students; programming classes are held in a lab that accomodates up to $$$b_{i, 1}$$$ students; and P. E. classes are held in a gym having enough place for $$$c_{i, 1}$$$ students. Analogically, the auditorium, lab and gym for the second subgroup can accept no more than $$$a_{i, 2}$$$, $$$b_{i, 2}$$$ and $$$c_{i, 2}$$$ students, respectively.
As usual, some students skip some classes. Each student considers some number of subjects (from $$$0$$$ to $$$3$$$) to be useless — that means, he skips all classes on these subjects (and attends all other classes). This data is given to you as follows — the $$$i$$$-th group consists of:
- $$$d_{i, 1}$$$ students which attend all classes;
- $$$d_{i, 2}$$$ students which attend all classes, except for P. E.;
- $$$d_{i, 3}$$$ students which attend all classes, except for programming;
- $$$d_{i, 4}$$$ students which attend only maths classes;
- $$$d_{i, 5}$$$ students which attend all classes, except for maths;
- $$$d_{i, 6}$$$ students which attend only programming classes;
- $$$d_{i, 7}$$$ students which attend only P. E.
There is one more type of students — those who don't attend any classes at all (but they, obviously, don't need any place in auditoriums, labs or gyms, so the number of those students is insignificant in this problem).
Your task is to divide each group into two subgroups so that every auditorium (or lab, or gym) assigned to each subgroup has enough place for all students from this subgroup attending the corresponding classes (if it is possible). Each student of the $$$i$$$-th group should belong to exactly one subgroup of the $$$i$$$-th group; it is forbidden to move students between groups.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 300$$$) — the number of groups.
Then the descriptions of groups follow. The description of the $$$i$$$-th group consists of three lines:
- the first line contains three integers $$$a_{i, 1}$$$, $$$b_{i, 1}$$$ and $$$c_{i, 1}$$$ ($$$1 \le a_{i, 1}, b_{i, 1}, c_{i, 1} \le 3000$$$) — the capacity of the auditorium, lab and gym assigned to the first subgroup of the $$$i$$$-th group, respectively;
- the second line contains three integers $$$a_{i, 2}$$$, $$$b_{i, 2}$$$ and $$$c_{i, 2}$$$ ($$$1 \le a_{i, 2}, b_{i, 2}, c_{i, 2} \le 3000$$$) — the capacity of the auditorium, lab and gym assigned to the second subgroup of the $$$i$$$-th group, respectively;
- the third line contains integers $$$d_{i, 1}$$$, $$$d_{i, 2}$$$, ..., $$$d_{i, 7}$$$ ($$$0 \le d_{i, j} \le 3000$$$) — the number of students belonging to each of the seven aforementioned types in the $$$i$$$-th group. It is not guaranteed that the sum of these values is positive — a group can consist entirely of students that don't attend classes at all.
It is guaranteed that the total number of students in all groups is not greater than $$$3000$$$.
For each group, print the result of its division as follows:
- if it is impossible to divide the group, print one integer $$$-1$$$;
- otherwise print seven integers $$$f_{i, 1}$$$, $$$f_{i, 2}$$$, ..., $$$f_{i, 7}$$$ ($$$0 \le f_{i, j} \le d_{i, j}$$$) — the number of students the first, second, ..., seventh type in the first subgroup of the $$$i$$$-th group (all other students will be assigned to the second subgroup). If there are multiple answers, print any of them.
3 9 4 13 1 10 3 1 2 3 4 5 6 7 9 4 13 1 10 3 2 1 3 4 5 6 7 1 2 3 4 5 6 0 0 0 0 0 0 0
1 1 3 4 2 0 7 -1 0 0 0 0 0 0 0