In Episode III of Star Wars (whose alleged title is How I became Vader), R2-D2 (Artoo-Detoo) 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 Ci arrive one at a time with some volume vi (expressed in cubic femtoparsec). R2-D2 wants to minimize the number of starships used for a given sequence of containers. Smart as he is, R2-D2 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 S0, S1, etc.. When container Cj arrives, select the starship of minimal index i that can contain Cj and put it in Si. In some sense, this heuristics minimizes the move of the container arriving before its loading. At the end of the n arrivals, R2-D2 counts the number s of starships used and he measures the total waste w of the sequence. For i = 0..s − 1, the waste in starship i is given by the unused volume. Your task is to simulate the algorithm of R2-D2. Input Input consists of several test cases, each of them following the description below. A blank line separates two consecutive cases. Each test case begins with capacity K on a line (K ≤ 1000), followed by the number of containers in the sequence, n on the second line (1 ≤ n ≤ 106). There are two possible formats for the remaining lines. If it contains one integer, then this is the next vi. 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 For each test case, your program must output the number s of starships used, followed by a blank, followed by the total waste w. The outputs of two consecutive cases will be separated by a blank line. Note: In the first sample input below, you load starship S0 with 50 and 25 and starship S1 with 70, so that the waste is (100-75)+(100-70)=55. The answer must be ‘2 55’ The second case which corresponds to the sequence 50, 40, 40, 20. S0 will contain 90, S1 will contain 60, so that the waste is 10+40=50 and the answer will be: ‘2 50’. Sample Input 100 3 50 25 70 100 4 50 b 2 40
2/2 20 Sample Output 2 55 2 50