The Enchanted Glasses
All submissions for this problem are available.
One day while roaming the lands of Greece, Rubixius came across a strange arrangement of glasses. He saw N glasses kept randomly with a cloud hovering over a glass ni for a certain period of time pouring 1 drop of rain per second. After the time was up it would go to another glass and start dripping water in that glass.
The strange thing about these glasses was that, if at any time a glass was filled to the brim it would spill into the next glass and the last glass would spill into the First glass. The thing that he found stranger was that each glass could only hold up to ci drops of overflow water after which the overflow water would vanish if the glass was not full.
Help Rubixius figure out how many drops of water all the glasses hold after time T.
The input starts with an integer S specifying the number of test cases. Each case will start with N and T which will specify the number of glasses and the total time respectively. The next line will contain the capacity ni of each glass. The following line will have the overflow limit ci for each glass. The last line of the case will have pairs of integers which will be in the form - gi ti - indicating the glass over which the cloud is hovering and for the period which it hovers. The input for each case is such that the total of all the time periods indicated on the last line of the test case will equal the total time T.
Output a single line for each case containing the maximum drops that are accumulated after time T.
Input: 2 5 8 1 1 1 1 1 1 1 1 1 1 0 8 5 8 2 1 1 1 1 1 1 1 1 1 0 8 Output: 5 6
|Time Limit:||0.230769 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.