For the convenience of Hogwarts students, it is decided to
extend the railway from Hogsmeade station to the castle's
gates. The magic N-track railway will take students
right to the castle, which will be quite appropriate
because of the increased frequency of attacks on people
after Voldemort's return. The railway is to be built of
rails of fixed length, which can be cut and joined.
When two rails or rail pieces are joined, a joint appears.
The Hogwarts Headmaster wants the number of joints to be minimal,
and if this conditions is satisfied, then the number of the used
rails should be minimal.
Input
The first line contains the number of the tracks of the magic railway N (1 ≤ N ≤ 18). The second line contains the length of the required railway in meters S (1 ≤ S ≤ 10000). The third line contains the length of a rail in meters L (10 ≤ L ≤ 10000). The lengths are given up to the tenths of a millimeter.
Output
Output the minimal number of rails needed to lay an N-track railway of the given length with the minimal number of joints.
Sample
input | output |
---|
3
1005.6712
20.0001
| 151
|
Problem Author: Stanislav Vasilyev
Problem Source: The Xth Urals Collegiate Programing Championship, March 24-25, 2006