Medium Divide and Conquer > Dynamic Programming

Many of us prefer to eat egg, banana, and bread as breakfast. **Kauser** has gone to market to bring these items. Problem is that he only has **T** taka in his pocket. He wants to utilize as much his money as possible to bring breakfast such that the amount of Bread he buys should be greater than amount of Banana he buys and the amount of Banana he buys should be greater than amount of Egg he buys. The amount of each of Egg, Banana and Bread must be **at least one**. The price of one egg costs **X** taka, the price of one banana costs **Y** taka and the price of one bread costs **Z** taka. Market price is so much expensive that **you will not get anything else less than 10 taka**. Your task is to help Kauser to utilize as much money as possible and tell him the minimum money he will save in his pocket after buying breakfast. If he can not buy breakfast maintaining above strategy print **-1**. Input: ------ Input starts with an integer **TC (1<=TC<=10)**, denoting the number of test cases. Each case begins with a line containing 3 integers say **X,Y,Z**. Then, there will be next line contains single integer value **T**. Output: ------- For each case of input, output a value as described in the problem statement. Constraints: ------- **10<=X,Y,Z<=100000** **1<=T<=1000000** Sample Input ------------ 1 10 10 10 63 Sample Output ------------- 3

Bishal Gautam