题目描述

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.

题目大意

题目描述

两个朋友阿尔伯特和巴尼来到新开的 Burrito King 厅。这家餐厅昨天刚刚开业，阿尔伯特收到了一张特殊的礼品卡，可以让他们免费得到一份墨西哥卷饼。然而，配料的数量是有限制的。第 $i$ 种配料最多可以含有 $g_i$ 克（$1\le i\le n$）。

每种成分都有两个满意度参数 $a_i$ 和 $b_i$。分别指每克相应成分的阿尔伯特获得的快乐量和每克巴尼获得的不快乐量。因此，阿尔伯特从墨西哥卷饼中获得的全部快乐等于：

$$\sum_{i=1}^{n}s_i\cdot a_i$$

巴尼对墨西哥卷饼的全部不快乐等于：

$$\sum_{i=1}^{n}s_i\cdot b_i$$

这里 $s_i$ 是墨西哥卷饼中第 $i$ 种配料分的克数。注意，$s_i$ 不一定是整数，并且 $0\le s_i\le g_i$。

阿尔伯特想让他从墨西哥卷饼中获得的全部快乐至少是 $A$。巴尼是他最好的朋友，所以阿尔伯特希望巴尼的全部不快乐不超过 $B$。在所有可能满足上述限制的卷饼中，阿尔伯特想选择一种能最大限度地增加他全部快乐的卷饼。

您的任务是帮助阿尔伯特选择 $s_i$ 来满足这些条件，或者发现没有解决方案。

输入格式

第一行包含三个整数 $N$、$A$ 和 $B$（$1\le N \le 10^{5},0\le A,B\le 10^{9}$）。

以下 $N$ 行都包含一种配料的描述：三个整数 $g_i$、 $a_i$、 $b_i$（$0\le g_i,a_i,b_i\le 100$），分别指第 $i$ 种配料的最大含有克数、每克阿尔伯特获得的快乐的量和每克巴尼获得的不快乐的量。

输出格式

输出的第一行必须包含两个实数，指满足问题陈述中的条件时，阿尔伯特能获得的最大快乐量和巴尼的不快乐量，或者 -1（如果阿尔伯特不能满足条件）。

如果条件可以满足，第二行包含 $N$ 个实数 $s_i$，单位为克。

您的输出必误差最多为 $10^{-8}$。任何满足给定条件的方法都判为正确。

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.