SP27039 EIUASSEMBLY - Assembly line

The Alternate Control Machine (ACM) Factory has a large assembly line to make a type of product. The assembly has N robots (R $ _{1} $ , R $ _{2} $ ...R $ _{N} $ ) working sequentially. That means a semi-finished product moves from robot R $ _{1} $ , to R $ _{2} $ , then to R $ _{3} $ ... to R $ _{N} $ . Each robot adds a component to the product. Each robot can complete its own job in P $ _{i} $ products per one hour. The company has a budget of M VNĐ to improve productivity for the entire assembly. As a product director, you know that robot R $ _{i} $ needs to invest M $ _{i} $ VNĐ to contribute to the production of one more product per hour. You have to optimize the amount of money to invest to each robot to produce maximum number of products per hour.

The first line of input contains one integer T (1 Then T test cases are given as follows:

For each test case, output in one line the maximum number of products the assembly can make after investing at most M VNĐ.