题目描述

内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。

经典的内存分配过程是这样进行的：

$\red{1}$、 内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从$\red{0}$开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址$\red{i}$开始的$\red{s}$个连续的内存单元称为首地址为$\red{i}$长度为$\red{s}$的地址片。

$\red{2}$、 运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻$\red{T}$，需要内存单元数$\red{M}$及运行时间$\red{P}$。在运行时间$\red{P}$内（即T时刻开始，$\red{T+P}$时刻结束），这$\red{M}$个被占用的内存单元不能再被其他进程使用。

$\red{3}$、假设在T时刻有一个进程申请$\red{M}$个单元，且运行时间为$\red{P}$，则：

$\red{~~1}$. 若T时刻内存中存在长度为M的空闲地址片，则系统将这$\red{M}$个空闲单元分配给该进程。若存在多个长度为$\red{M}$个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。

$\red{~~2}$. 如果T时刻不存在长度为$\red{M}$的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为$\red{M}$的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

输入格式

第一行是一个数$\red{N}$，表示总内存单元数（即地址范围从$\red{0}$到$\red{-1}$）。

从第二行开始每行描述一个进程的三个整数$\red{T、M、P（M <= N）}$。

最后一行用三个$\red{0}$表示结束。

数据已按T从小到大排序。

输入文件最多$\red{10000}$行，且所有数据都小于$\red{10 ^9}$ 。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出格式

输出包括$\red{2}$行。

第一行是全部进程都运行完毕的时刻。

第二行是被放入过等待队列的进程总数。

样例

输入样例

10
1 3 10
2 4 3
3 4 4
4 1 4
5 3 4
0 0 0

输出样例

12
2

提示