题目描述

Two friends Albert and Barney came to the newly opened restaurant Burrito King. The restaurant had opened just yesterday, and Albert has got a special gift card, which allows the friends to get a free burrito. However, there is a constraint on the amount of ingredients -- the burrito can contain at most $g_i$ grams of ingredient \(i\) for all \(i\) from $1$ to \(n\).

There are two satisfaction parameters \(a_i\) and \(b_i\) for each ingredient -- the amount of Albert's joy per gram of the corresponding ingredient, and the amount of Barney's unhappiness per gram, correspondingly.

Therefore, the total Albert's joy from the burrito is equal to:

\[\su_m_{i=1}^{n}{s_i \cdot a_i}\]

The total Barney's unhappiness from the burrito is equal to:

\[\su_m_{i=1}^{n}{s_i \cdot b_i}\]

Here \(s_i\) is the number of grams of the \(i\)-th ingredient in the burrito. Note, that \(s_i\) is not necessarily an integer, and 0 \le \(s_i\) \le \(g_i\).

Albert wants to make his total joy from the burrito to be at least \(A\). Barney is his best friend, so Albert wants Barney's total unhappiness to be no more than \(B\). Among all possible burritos that satisfy the above constrains, Albert wants to choose one that maximises his total joy.

Your task is to help Albert to choose \(s_i\) to satisfy these conditions or to find out that there is no solution.

输入格式

The first line contains three integers \(n\), \(A\), and $\(B\) (1 \le \(n\) \le 100 000 , 0 \le \(A\), \(B\) \le 10^{9}),$ the number of ingredients, the least amount of Albert's joy and the maximal amount of Barney's unhappiness. Each of the following \(n\) lines contains a description of an ingredient: three integers $\(g_i\), \(a_i\), \(b_i\) (0 \le \(g_i\), \(a_i\), \(b_i\) \le 100)$ -- the maximal number of grams allowed, the amount of Albert's joy per gram and the amount of Barney's unhappiness per gram.

输出格式

The first line of the output must contain two real numbers -- the maximal amount of his joy and the amount of Barney's unhappiness that Albert can obtain, satisfying the conditions in the problem statement, or $`−1 −1`,$ if Albert cannot satisfy the conditions.

If the conditions are satisfiable the second line must contain \(n\) real numbers -- the amount of each ingredient in grams.

Your output must have an absolute or relative error of at most $10−8$ .

Any way to reach maximal Albert's joy that satisfies the given conditions can be printed.

2 5 5
2 2 1
2 2 4

5.5 5
2 0.75

2 5 5
2 2 2
2 2 4

-1 -1

提示

Time limit: 1 s, Memory limit: 256 MB.