For each variant consider all prefixes of tasks. It is optimal to copy the task that takes most time, so we keep track of maximal time and calculate the sum S of t_ij of the prefix. If the maximal time is greater than t₀ it is better to copy this task, getting the total time needed be S - max(0, M - t₀). Now compare this value to t to check whether it is possible to write down that many tasks for this variant.

First sort all notes based on the number of left legs. Then iterate over this array. If the centipede has l_i left legs, then first i notes can be correct, and other notes are definitely incorrect (we can ignore the fact that some notes have the same l_i, we will find the answer considering them).

Now we want to find out how many of the first i notes can be correct. Note with number j ≤ i can be correct if r_j ≤ n - l_i. This problem is quite standard, we can solve it using, for example, Internal Tree.

To minimize the number of days Basil needs, we need to minimize the height of the resulting tree. If the depth of the leaf in the resulting tree is h, Basil needs 2^h - 1 - n days to create the required number of vertices.

Note that if the tree has a vertex of degree greater than 3, it is impossible to fulfill the task, because in a complete binary tree every vertex has at most 3 neighbors. Also note that the root vertex must have two sons.

So let us try all vertices with degree not greater than 2 and try it as a root. Choose vertex which results in the smallest tree height.

Finding the most distant vertex for each vertex in a tree is a well known trick. Choose vertex 0 as a root and run dfs(0). First find h[v] for each vertex — the length of the longest path down starting from v. Then run dfs2(0) passing the longest path up[v] to a vertex v through its parent. To find it when running dfs2(x) from y we choose maximum among up[y] + 1, and maximal value of h[z] + 2 for all children z of y except x.

The solution proceeds in several rounds.

• If sum(min_i) > sum(v_i) — the answer is «NO»;
• If sum(max_i) < sum(v_i) — the answer is «NO»;
• Pour min_i·p_i / 100 of c_i to each container;
• For each reagent i sort containers that have c_j = i by increasing p_j and pour the rest of reagent i to them;
• Pour (max_j - min_j)·p_j / 100 of reagent c_j to the container j;
• The rest of reagents can be put to containers arbitrarily;
• If after doing so there is still extra liquid the answer is «NO»;
• Some containers may still have not enough liquid.
• Consider such container i, first pour from other container reagents other than this container is marked by, not making it contain less then min_j of liquid
• If it is still not enough, we can now move liquid c_j from container j, it will not ruin percentage condition any more.

Now the resulting distribution of reagents satisfies all required conditions.

Final note: there could be precision troubles in this problem. Although there were no such tests, they are possible, Petr Mitrichev (congratulations on winning the round!) found such test after the contest. We understand that this is not good, and will try to avoid such problems in future.

Let us first solve the following problem: find the minimal amount of money that cannot be paid by a set of coins. Let us first consider that we have no coins and the maximal amount we can pay is 0.

Let us describe the step when we have considered all coins with the value not exceeding X and we can pay any sum up to Y, inclusive. Let the total cost of coins with value greater than X, but not exceeding Y + 1, be sum. Then if sum = 0, we cannot represent Y + 1 with this set. In the other case we can move to the state where we have considered coins with the value not exceeding Y + 1, and we can pay any sum up to Y + sum, inclusive.

Now we see, that the value of the greatest considered coin grows as Fibonacci numbers, so the process terminates in at most O(log Answer) iterations.

So what we need to do now is to find the sum of numbers not exceeding X at a segment. This can be done using Interval Tree, the final complexity is O(m log n log Answer).

The answer is «NO» only if d is not divisible by the greatest common divisor of all a_i. In any other case the answer exists. First let us create any array that satisfies a₁·x₁ + a₂·x₂ + ... + a_n·x_n = d, but not necessarily other conditions. To do this divide all a_i and d to gcd(a₁, ..., a_n). If n = 1, then x₁ = d / a₁. In other cases find the corresponding values for any prefix [1, p] such values x_i, p that a₁ x_1, p + ... + a_p x_p, p = gcd(a₁, ..., a_p). Use induction. Set x_1, 1 = 1. If we have x_i, p and want to find x_{i, p + 1}. Use extended Euclid algorithm to find s and t: s·gcd(a₁, ..., a_p) + t·a_p + 1 = gcd(gcd(a₁, ..., a_p), a_p + 1) = gcd(a₁, ..., a_p + 1). Then for i ≤ p x_{i, p + 1} = s·x_i, p and x_{p + 1, p + 1} = t. Getting x_i, n, find x_i = d / gcd(a₁, ..., a_n)·x_i, n = d·x_i, n. This solution takes O(n²), and doesn't finish in time limit. To decrease the time complexity, first find subset of a_i that has gcd equal to 1. Iterate over a_i and add the current a_i to the set if it decreases the number of different divisors. Such subset would contain at most 7 elements. Use the algorithm described above for this set, for other elements set x_i = 0.

Now the algorithm is fast, but the conditions for x_i are not satisfied: they can exceed 10⁶ by their absolute value and there can be zeroes. Now let us normalize the values. First let us decrease x_i to not exceed 10⁶. To do this make x_i non-negative, and less then a₁ for all i > 1. This can be done by the following operation: subtract ka_i from x₁ and add ka₁ to x_i where k = (x_i mod a₁ - x_i) / a₁. Note that the results of this operation can be stored in 64-bit integers, because x₁ cannot exceed |d - a₂ x₂ - ... - a_n x_n| < 10⁶·10⁶·10⁵. Now consider x_i starting from the second one, and for each one do the following: subtract a₁ from x_i and add a_i to x₁. Note that there exists i, such that after applying the operation to x₁, ..., x_i we have 0 ≥ x₁ ≥  - 10⁶. Now we have |x_i| ≤ 10⁶, so everything that is left is to get rid of zeroes. Let us pair all zeroes to each other, except probably one if the number of zeroes is odd. For each such pair (i, j) set x_i = a_j and x_j =  - a_i. We probably have one index p left such that x_p = 0. Consider several cases:

• If there exists x_j such that it is not equal to a_p by its absolute value, then apply the following operation: subtract sign(x_j)a_p from x_j and add sign(x_j)a_j to x_p.
• If there is no such x_j, but a_p ≤ 5·10⁵, for any x_j we can apply the following operation: add sign(x_j)a_p to x_j and subtract sign(x_j)a_p from x_p.
• Finally if none of the above is true there must be a_q, such that a_q ≠ a_p. Now do the following: subtract sign(x_j)a_p from x_q and add sign(x_j)a_q to x_p. Now x_q is zero. But if n > 2, it is the first case for q, if n = 2 it is the second case for q.

Finally note that we must make this normalization must be performed for each prefix in the algorithm described in the first paragraph, so that the intermediate results fit 64-bit type. See judges solution for more details.