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
Shivam Mishra:
20150131 00:04:23
Can Vj > K ??

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 