Growing Mushrooms

2000ms

262144K

Description:

Each year in the castle of Dwarven King there is a competition in growing mushrooms among the dwarves. The competition is one of the most prestigious ones, and the winner gets a wooden salad bowl. This year's event brought together the best mushroom growers from around the world, so we had to slightly change the rules so that the event gets more interesting to watch.

Each mushroom grower has a mushroom that he will grow on the competition. Under the new rules, the competition consists of two parts. The first part lasts t₁ seconds and the second part lasts t₂ seconds. The first and the second part are separated by a little break.

After the starting whistle the first part of the contest starts, and all mushroom growers start growing mushrooms at once, each at his individual speed of v_i meters per second. After t₁ seconds, the mushroom growers stop growing mushrooms and go to have a break. During the break, for unexplained reasons, the growth of all mushrooms is reduced by k percent. After the break the second part of the contest starts and all mushrooms growers at the same time continue to grow mushrooms, each at his individual speed of u_i meters per second. After a t₂ seconds after the end of the break, the competition ends. Note that the speeds before and after the break may vary.

Before the match dwarf Pasha learned from all participants, what two speeds they have chosen. However, the participants did not want to disclose to him all their strategy and therefore, did not say in what order they will be using these speeds. That is, if a participant chose speeds a_i and b_i, then there are two strategies: he either uses speed a_i before the break and speed b_i after it, or vice versa.

Dwarf Pasha really wants to win the totalizer. He knows that each participant chooses the strategy that maximizes the height of the mushroom. Help Dwarf Pasha make the final table of competition results.

The participants are sorted in the result table by the mushroom height (the participants with higher mushrooms follow earlier in the table). In case of equal mushroom heights, the participants are sorted by their numbers (the participants with a smaller number follow earlier).

Input:

The first input line contains four integer numbers n, t₁, t₂, k (1 ≤ n, t₁, t₂ ≤ 1000; 1 ≤ k ≤ 100) — the number of participants, the time before the break, the time after the break and the percentage, by which the mushroom growth drops during the break, correspondingly.

Each of the following n lines contains two integers. The i-th (1 ≤ i ≤ n) line contains space-separated integers a_i, b_i (1 ≤ a_i, b_i ≤ 1000) — the speeds which the participant number i chose.

Output:

Print the final results' table: n lines, each line should contain the number of the corresponding dwarf and the final maximum height of his mushroom with exactly two digits after the decimal point. The answer will be considered correct if it is absolutely accurate.

Sample Input:

2 3 3 50
2 4
4 2

Sample Output:

1 15.00
2 15.00

Sample Input:

Sample Output:

Note:

First example: for each contestant it is optimal to use firstly speed 2 and afterwards speed 4, because 2·3·0.5 + 4·3 > 4·3·0.5 + 2·3.

Informação

Provedor Codeforces

Código CF186B