B :: Budget
Time Limit: 1 Second Memory Limit: 65536 KB
The Amirkabir annual contest is held every year to choose teams participating in Tehran regional contest. This year the responsibility of supplying the budget is on “Salim Khan”. After tiresome pursuits of Salim Khan, university agreed to pay V Rials for the contest’s expenditure. Hence, The financial manager of the university has deposited the money into Salim Khan’s bank account. However, since they don’t like Salim Khan, they have forced him to withdraw the money only through ATM machines.
ATM machines support two different transactions:
Money withdrawal: take some money in cash out of a bank. Limited to at most R Rials for each account in each day.
Money Transfer: transfer money to another account. No limitations on the amount of money transferred, but the bank charges C Rials for each transfer transaction. The transfer fee is taken from the transferor account.
Salim Khan needs N Rials in order to buy T‐shirts for the contests and wants to withdraw the money from his bank account as soon as possible. Salim Khan has K bank accounts (counting the first one) and is willing to use all of them if needed. Help him to find the least number of days he needs to withdraw N Rials out of his bank accounts.
Input
The first line of input contains a single integer T (T ≤ 200), the number of tests. Each test will be in a separate line containing 5 integers V, N, R, C and K. (1 ≤ N ≤ V ≤ 107, 0 ≤ R, C ≤ 107, 1 ≤ K ≤ 20) — as explained in problems statement.
Output
For each test case, in a separate line, output the number of days that Salim Khan needs to withdraw the money for T‐shirts. If he will never be able to buy T‐shirts for the contest, print “Contest without T-shirts!” (Quotes for clarity).
Sample Input
2 500 400 200 5 5 1000 990 80 20 10
Sample Output
1 13Submit
Source: AUT 2012