In the ancient ruins of the Tomb of the Kings in Paphos, echoes propagate through a network of chambers connected by tunnels. The network is a tree-like structure with $$$n$$$ chambers and $$$n-1$$$ tunnels. The entrance is located at chamber 1.
Each chamber contains an ancient artifact activated by the sound of echo. To activate the artifact in chamber $$$i$$$, the strength of echo in this chamber must be at least $$$d_i$$$.
The strength of the echo is an integer number. It may be both positive or negative. The echo starts at the entrance (chamber 1) with strength 0 and spreads throughout tunnels in the direction from the entrance. Every time the echo moves through a tunnel, its strength decreases by $$$1$$$.
To increase the strength of the echo, you may use special resonators. If you put a resonator in some chamber, the strength of echo in this room will be increased by one. This amplified echo will then be moving forward to further chambers, so as a result, the strength of the echo in all reachable chambers will be increased by one.
 |  |
| Echo strength without resonators | Echo strength with one resonator in chamber 4 |
You can put at most $$$F$$$ resonators in each chamber.
Your task is to find the minimal number of resonators needed to activate all the artifacts.
The first line of the input contains integers $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) and $$$F$$$ ($$$0 \le F \le 2 \cdot 10^9$$$).
The second line contains $$$n$$$ integers $$$d_1 \ldots d_n$$$ ($$$|d_i| \le 10^9$$$).
The next $$$n-1$$$ lines each contain two integers $$$u$$$, $$$v$$$ meaning that a tunnel exists between chambers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$).
Output one integer: the minimal number of resonators needed to make the echo strength reaching each chamber $$$i$$$ at least $$$d_i$$$.
If it is impossible to activate all the artifacts, output $$$-1$$$.
This task contains four subtasks. To get the points for the subtask, your solution should pass all the tests in the corresponding subtask.
| Subtask | Constraints | Points |
| $$$1$$$ | $$$n \le 8$$$, $$$F \leq 5$$$ | $$$12$$$ |
| $$$2$$$ | For each $$$i$$$ from 1 to $$$n-1$$$, nodes $$$i$$$ and $$$i+1$$$ are connected with a tunnel | $$$25$$$ |
| $$$3$$$ | $$$F = 2 \cdot 10^9$$$ | $$$13$$$ |
| $$$4$$$ | $$$F = 0$$$. | $$$9$$$ |
| $$$5$$$ | $$$n \le 1000$$$ | $$$16$$$ |
| $$$6$$$ | No additional constraints | $$$25$$$ |
6 22 -1 0 2 0 11 41 52 44 33 6
4
2 01000000000 -11 2
-1
5 3-2 1 5 3 24 13 54 23 1
7
Here is an illustration for the first example.
Marikkou is spending her afternoon with her grandmother, who is teaching her how to sew lefkaritika—a traditional type of Cypriot lace. These laces are made by tying tiny knots and joining them with threads to form delicate designs.
There are many patterns in lefkaritika, but Marikkou is most fascinated by the ones built entirely from knots and threads. She begins with a simple rectangular frame of knots, arranged in an $$$n \times m$$$ grid (all evenly spaced). From there, she can add new knots inside the frame and connect them to existing ones with threads, slowly weaving the lace.
Example of lefkaritiko for $$$n=5$$$ and $$$m=4$$$.
As she experiments, Marikkou discovers that not every design works: the lace must be sturdy. After some careful thought and experimentation, she makes up the rules for which patterns are allowed:
- All the knots on the outer $$$n \times m$$$ frame must be used.
- The threads may only form triangles.
- All the triangles must have angles less than or equal to 90 degrees.
- A knot that serves as a corner of one triangle cannot lie along the side of another triangle.
- New knots may only be placed at points with integer coordinates.
Here are some examples of correct and incorrect lefkaritika:
- a: incorrect, the knot on the frame is not used.
- b: incorrect, the part is not a triangle.
- c: incorrect, the angle is greater than 90 degrees.
- d: incorrect, the knot is on a side of another triangle.
- e: correct, 12 triangles.
- f: correct, 10 triangles.
Marikkou believes that the fewer triangles she uses, the more elegant the lefkaritiko becomes. She wonders what pattern will give her the smallest number of triangles while still holding together firmly. Can you help her sew the perfect lefkaritiko?
This is an output-only task. Download the 20 input files (01.txt, 02.txt, up to 20.txt) containing the inputs from the contest system, solve the task, and submit the output as separate files. You need to submit a zip file called containing files 01.out, 02.out, etc.
The single line of the input contains two integers $$$n$$$ and $$$m$$$, the width and the height of the frame.
In the first line output integer $$$t$$$, the number of threads used. In the next $$$t$$$ lines output 4 integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$, the coordinates of two knots connected with a thread.
Your score for the task will be the sum of your score on each of the 20 testcases 01.txt through 20.txt. Each testcase is worth up to 5 points.
If your answer for the test is incorrect, you will get 0 points. If it is correct, then your score $$$S$$$ for this test will be calculated using the following formula:
$$$S = 5 \cdot (0.05 + 0.95\cdot \min(\frac{T_{opt}}{T}, 1))$$$
Here $$$T$$$ is the number of triangles in your solution, and $$$T_{opt}$$$ is the number of triangles in the best solution found by judges.
2 3
9 0 0 0 1 0 1 0 2 1 0 1 1 1 1 1 2 0 0 1 0 0 2 1 2 0 1 1 0 0 1 1 1 0 2 1 1
Here is a picture for the example:
When Onisilos of Salamis rose to free his land, an oracle told him: "To win, you must divide your power in two yet keep your spirit whole." At first, Onisilos was puzzled by this phrase, but later realized its meaning.
The army of Onisilos consists of $$$n$$$ soldiers. Onisilos defines the spirit of the army of size $$$x$$$ as the sum of digits of the number $$$x$$$ in decimal notation. For example, the spirit of the army of size 243 is $$$s(243)=2+4+3=9$$$.
Onisilos needs to split his army into two parts, such that each part has the same spirit as the whole army. In other words, you need to find integers $$$a$$$ and $$$b$$$ such that:
- $$$n = a + b$$$, and
- $$$s(a) = s(b) = s(n)$$$, where $$$s(x)$$$ is the sum of digits of the number $$$x$$$ in decimal notation.
For example, if $$$n=243$$$, you can choose $$$a=216$$$ and $$$b=27$$$, so $$$243=216+27$$$, and $$$2+1+6=2+7=2+4+3$$$.
The input contains one integer $$$n$$$ without leading zeroes ($$$1\le n \lt 10^{100000}$$$). Note that this number may be huge.
Print two integers $$$a$$$ and $$$b$$$ that satisfy the required properties. If there are multiple solutions, output any. If there is no solution, output $$$-1$$$.
This task contains four subtasks. To get the points for the subtask, your solution should pass all the tests in the corresponding subtask.
| Subtask | Constraints | Points |
| $$$1$$$ | $$$n \le 10^{6}$$$ | $$$10$$$ |
| $$$2$$$ | $$$n \le 10^{50}$$$ | $$$20$$$ |
| $$$3$$$ | $$$n \le 10^{1000}$$$ | $$$30$$$ |
| $$$4$$$ | no additional constraints | $$$40$$$ |
243
216 27
42
-1