HELPR2D2  Help R2D2!
In Episode III of Star Wars (whose alleged title is "How I became Vader"), R2D2 (ArtooDetoo) is again confronted to a tedious work.
He is responsible for the loading of the republic transport starships in the fastest way. Imagine a huge space area where n starships are parked.
Each starship has a capacity of K cubic femtoparsec. Containers C_{i} arrive one at a time with some volume v_{i} (expressed in cubic femtoparsec).
R2D2 wants to minimize the number of starships used for a given sequence of containers.
Smart as he is, R2D2 knows for sure that the problem is a hard one, even with the force being around.
Here is the heuristics he selected to solve his problem. Start with all starships ready to load, and numbered S_{0},S_{1},etc.
When a container C_{j} arrives, select the starship of minimal index i that can contain C_{j} and put it in S_{i}.
In some sense, this heuristic minimizes the move of the container arriving before its loading.
At the end of the n arrivals, R2D2 counts the number s of starships used and he measures the total waste w of the sequence.
For i=0..s1, the waste in starship i is given by the unused volume.
Your task is to simulate the algorithm of R2D2.
Input
The first line of the input contains a number T ≤ 10 that indicates the number of test cases to follow. Each test case begins with K on a line (K ≤ 1000), followed by the number of containers in the sequence, n, on the second line (1 ≤ n ≤ 1000000). There are two possible formats for the remaining lines. If it contains one integer, then this is the next v_{i}. If it begins with the character b (for block), it is followed by 2 integers r and v. This means that the r next containers arriving have volume v.
Output
Your program must output the number s of starships used, followed by a blank, followed by the total waste w.
You can assume, that at most 100000 starships are needed, and R2D2 has to change the starships in which the next container is loaded at most 100000 times.
Example
Input: 2 100 3 50 25 70 100 4 50 b 2 40 20 Output: 2 55 2 50
hide comments
yaseenmollik:
20200809 20:27:13
Segment Tree +Binary Search :D 

sawchawn:
20200513 19:19:13
could you have written a longer problem statement! fed up 

tri_cep1:
20200420 17:54:14
why tf time limit is 7 sec 

coolio_1:
20200226 19:31:16
Was afraid of this problem when I read it initially. Ended up solving it in 1 go with Seg tree. Also, interesting i/p format :) 

thekidnamedme:
20180927 21:14:35
Ok so something weird is happening, SPOJ always seems to replace one instance of a variable that happens to be in a scanf statement by a stray '×' character regardless of whether the code gives a wa or an ac. Really curious to know why this is happening :/ 

luka_dzimba911:
20180809 11:46:46
334 lines , modified AVL tree , 3 days , ugliest code ever


anubhawiiitu:
20171224 15:51:36
Not so good problem due to ample time(7s) 

sxie12:
20170706 18:37:59
Use scanf and printf if you're using C++. 

Vineet Setia:
20160605 21:59:40
how can we know if input is int or char ? 

spoj2121:
20151225 13:02:37
nice question (y)

Added by:  Adrian Kuegel 
Date:  20040714 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM Southwestern European Regional Contest, Paris 2003 