ZOJ Problem Set - 3021
watashi is a sport lover and he selects different kind of PE every semester. Usually he is satisfied with his choose, but this term, after the first badminton class started, he gets mad with the teacher "Satan. ChenTooBad" at his snap at the students with no reason at the first sight of them.
watashi will revenge to "Satan. ChenTooBad"'s impertinence. Finally, the end of semester comes, the students have right to estimate the teacher. That's the revenge moment, watashi thought.
Each student can give an integer mark form 1 to N to the teacher he/she is estimating. A teacher's rating is the average of marks given by students rounded to 0.1 (for example, 8.34 is rounded to 8.3, and 8.65 and 8.68 are rounded to 8.7). watashi knows "Satan. ChenTooBad" has been valued by M visitors and its current rating is K (rounded).
If a teacher's rating is not greater than L, he/she will be fired. Evil watashi wants to drag "Satan. ChenTooBad" out of his university as the final revenge.
Now watashi only knows the four numbers, can you help watashi to determine how many votes watashi must cast in order to achieve the revenge (assure that Satan will be fired).
Each block has only one line. It contains four numbers N, K, L and M. The numbers K, L are given with one fractional digit. 1 <= N <= 100. 1 <= K, L <= N. 1 <= M <= 1000000.
You can make sure that the input is always valid (K is achievable by M visitors).
Output the minimal number of estimates that guarantee that "Satan. ChenTooBad "will be fired. If it is impossible to achieve, just output "-1".
10 5.1 4.6 50
Author: OUYANG, Jialin
Source: ZOJ Monthly, August 2008