题目描述

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

经典的内存分配过程如下：

1. 内存单元

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

2. 进程占用内存

   • 运行过程中有若干进程需要占用内存。
   • 每个进程有三个属性：申请时刻$T$、需要的内存单元数$M$、运行时间$P$。
   • 在运行时间$P$内（即从$T$时刻开始，到$T+P$时刻结束），这$M$个被占用的内存单元不能被其他进程使用。

3. 内存分配规则

   • 在$T$时刻，若有一个进程申请$M$个内存单元，运行时间为$P$，则：
     1. 如果$T$时刻存在长度为$M$的空闲地址片，则系统将该地址片分配给该进程。
        • 若有多个满足条件的地址片，选择首地址最小的进行分配。
     2. 如果$T$时刻没有足够的空闲地址片，则该进程被放入等待队列。
        • 等待队列中的进程按照**先进先出（FIFO）**原则处理。
        • 当某一时刻有足够的内存时，系统会立即为队首进程分配内存（优先级最高）。

输入格式

• 第一行是一个整数$N$，表示总内存单元数（地址范围$0$到$N-1$）。
• 接下来的若干行，每行描述一个进程的三个整数$T$、$M$、$P$（$M \leq N$）。
• 最后一行用三个$0$表示输入结束。
• 输入数据已按$T$从小到大排序。
• 输入最多$10000$行，所有数据均满足$0 \leq T, P \leq 10^9$。
• 同一行相邻数据之间可能有一个或多个空格分隔。

输出格式

• 第一行：所有进程运行完毕的时刻。
• 第二行：被放入过等待队列的进程总数。

示例输入

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

示例输出

12
2

题目来源

Noi 99