Shriraj and Debt
All submissions for this problem are available.
The month has a long way to go and Shriraj is in deep debt (again!). But this time he has an idea of earning some money. Shriraj has a very large water bottle and an collection of some water soluble compounds. He intends to make some solutions and sell them to earn money, he can also sell water directly.
Shriraj has n units of water and k different compounds which he has numbered 1 to k. Now he has collected data in different arrays w, x, y and c such that he has w[i] units of the ith compound. Now he can create a solution by mixing x[i] units of ith compound and y[i] units of water and sell this new solution for c[i] rupees. He also knows that he can sell a units of water for b rupees.
As Shriraj is forming this business plan, he realizes he will be needing an assistant for helping him. You have the honour of being chosen as his assistant and the first task assigned to you is to find his maximum earnings by selling solutions.
Since Shriraj is a slightly strange person, he requires you to follow exact procedures as above to create solutions i.e. partially creating or selling of solutions is not allowed (including water) (for example, you cannot use x[i]/2 units of water and y[i]/2 units of compound i to sell resulting solution for z[i]/2 units). You can however create and sell the solutions multiple times.
Note: Arrays w,x,y,c are 1-indexed.
Remaining water/compounds are discarded.
- The first line of input will contain number of test cases T.
- The first line of each test case will contain numbers n, k, a, b separated by a space.
- Then k lines will follow of which the ith line will contain numbers w[i], x[i], y[i], c[i] separated by a space.
For each test case, output a single integer which is Shriraj's maximum earnings in rupees in a new line.
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 1000
- 1 ≤ k ≤ 10
- 1 ≤ a,b ≤ 100
- 1 ≤ w[i],x[i],y[i],c[i] ≤ 100
Input: 1 10 3 1 1 1 3 2 10 2 1 2 1 5 1 3 2 Output: 10
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.