/ 
Time Limit: 3 sec / Memory Limit: 256 MB
配点: 300 点
問題文
すぬけ君はビーカーに砂糖水を作ろうとしています。 最初ビーカーは空です。すぬけ君は以下の 4 種類の操作をそれぞれ何回でも行うことができます。一度も行わない操作があっても構いません。
- 操作 1: ビーカーに水を 100A [g] 入れる。
- 操作 2: ビーカーに水を 100B [g] 入れる。
- 操作 3: ビーカーに砂糖を C [g] 入れる。
- 操作 4: ビーカーに砂糖を D [g] 入れる。
すぬけ君の実験環境下では、水 100 [g] あたり砂糖は E [g] 溶けます。
すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。
ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計) が F [g] 以下であり、 ビーカーの中に砂糖を溶け残らせてはいけないとき、 すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。 答えが複数ある場合はどれを答えても構いません。
水 a [g] と砂糖 b [g] を混ぜた砂糖水の濃度は \frac{100b}{a + b} [%]です。 また、この問題では、砂糖が全く溶けていない水も濃度 0 [%] の砂糖水と考えることにします。
制約
- 1 ≦ A < B ≦ 30
- 1 ≦ C < D ≦ 30
- 1≦ E ≦ 100
- 100A ≦ F ≦ 3,000
- A, B, C, D, E, F はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B C D E F
出力
整数を空白区切りで 2 つ出力せよ。 1 つ目は求める砂糖水の質量、2 つ目はそれに溶けている砂糖の質量とせよ。
入力例 1
1 2 10 20 15 200
出力例 1
110 10
この入力例の状況では、水 100 [g] あたり砂糖は 15 [g] 溶けます。 また、ビーカーに物質を 200 [g] まで入れることができます。
操作 1 と操作 3 を 1 回ずつ行うことで 110 [g] の砂糖水を作ることができます。 また、これ以上濃度の高い砂糖水を作ることはできません。 たとえば、以下のような操作は条件を満たしません。
- 操作 1 と操作 4 を 1 回ずつ行うと、ビーカーに砂糖が溶け残ってしまいます。
- 操作 2 を 1 回と操作 3 を 3 回行うと、ビーカーの中の物質の量が 200 [g] を超えてしまいます。
入力例 2
1 2 1 2 100 1000
出力例 2
200 100
ほかに、たとえば以下の出力も正解となります。
400 200
一方、以下の出力は不正解となります。
300 150
なぜなら、砂糖が 150 [g] 溶けた 300 [g] の砂糖水を作るにはビーカーに水をちょうど 150 [g] 入れる必要がありますが、そのようなことは不可能だからです。
入力例 3
17 19 22 26 55 2802
出力例 3
2634 934
Score : 300 points
Problem Statement
Snuke is making sugar water in a beaker. Initially, the beaker is empty. Snuke can perform the following four types of operations any number of times. He may choose not to perform some types of operations.
- Operation 1: Pour 100A grams of water into the beaker.
- Operation 2: Pour 100B grams of water into the beaker.
- Operation 3: Put C grams of sugar into the beaker.
- Operation 4: Put D grams of sugar into the beaker.
In our experimental environment, E grams of sugar can dissolve into 100 grams of water.
Snuke will make sugar water with the highest possible density.
The beaker can contain at most F grams of substances (water and sugar combined), and there must not be any undissolved sugar in the beaker. Find the mass of the sugar water Snuke will make, and the mass of sugar dissolved in it. If there is more than one candidate, any of them will be accepted.
We remind you that the sugar water that contains a grams of water and b grams of sugar is \frac{100b}{a + b} percent. Also, in this problem, pure water that does not contain any sugar is regarded as 0 percent density sugar water.
Constraints
- 1 \leq A < B \leq 30
- 1 \leq C < D \leq 30
- 1 \leq E \leq 100
- 100A \leq F \leq 3 000
- A, B, C, D, E and F are all integers.
Inputs
Input is given from Standard Input in the following format:
A B C D E F
Outputs
Print two integers separated by a space. The first integer should be the mass of the desired sugar water, and the second should be the mass of the sugar dissolved in it.
Sample Input 1
1 2 10 20 15 200
Sample Output 1
110 10
In this environment, 15 grams of sugar can dissolve into 100 grams of water, and the beaker can contain at most 200 grams of substances.
We can make 110 grams of sugar water by performing Operation 1 once and Operation 3 once. It is not possible to make sugar water with higher density. For example, the following sequences of operations are infeasible:
- If we perform Operation 1 once and Operation 4 once, there will be undissolved sugar in the beaker.
- If we perform Operation 2 once and Operation 3 three times, the mass of substances in the beaker will exceed 200 grams.
Sample Input 2
1 2 1 2 100 1000
Sample Output 2
200 100
There are other acceptable outputs, such as:
400 200
However, the output below is not acceptable:
300 150
This is because, in order to make 300 grams of sugar water containing 150 grams of sugar, we need to pour exactly 150 grams of water into the beaker, which is impossible.
Sample Input 3
17 19 22 26 55 2802
Sample Output 3
2634 934