题面描述

团队申请了一组服务器，用于机器学习训练。为了充分利用资源，需要实现一个任务调度算法。具体要求如下：

• 服务器与任务：

  • 有 $M$ 台空闲服务器。
  • 有 $N$ 个训练任务，每个任务有训练时间 $T$ 和优先级 $P$。

• 调度规则：

题目内容

团队申请了一组服务器,用于机器学习训练，为了充分利用资源，需要你来完成任务调度算法的实现。

一台服务器同一时间只能执行一个训练任务，每个训练任务有训练时间和优先级。

当空闲服务器不足时，优先执行高优先级的训练任务;如果多个训练任务的优先级相同，优先执行训练时间长的任务。

当空闲服务器充足时，可以同时执行不同优先级的训练任务。

所有任务在开始时刻(零时刻)一次性提交完毕，等待调度。任务一旦开始就不能暂停或更换服务器，直到任务结束。

现在需要根据服务器和训练任务，计算完成所有训练任务的总时间。

输入描述

第一行一个整数$M$，表示空闲服务器的数量，$1<=M<=10^3$

第二行一个整数$N$，表示训练任务的数量,$1<=N<=10^5$

从第三行开始连续$N$行，每行两个整数和$P$，分别表示对应任务的训练时间和优先级，$1≤T≤10^7$,$1≤P≤10$。

优先级$P$数值越小，表示优先级越高。

不需要考虑非法输入。

输出描述

完成所有训练任务的总时间

样例1

输入

2
4
1 1 
2 1 
2 2
4 2

输出

5

说明

$2$台服务器$4$个训练任务，为方便描述，假设2台服务器编号分别为$A、B$。

1、起始时刻为$0$，先同时执行两个优先级均为$1$的训练任务。$A$执行任务$T=1,F=1$;$B$执行任务-2，-1

2、在时刻$1$，$A$的任务执行完毕，继续执行优先级为$2$，并且执行时间较长的任务$T=4,P=2$

3、在时刻$2$，$B$的任务执行完毕，执行剩余的一个任务$T=2,P=2$。

4、在时刻$4$，$B$的任务执行完毕，没有未执行的任务。

5、在时刻$5$，$A$的任务执行完毕，没有未执行的任务。

训练完成的时刻即需要的总时间为$5$，输出$5$。

样例2

输入

3
3
1 1
2 2
3 3

输出

3

说明

$3$台服务器$3$个训练任务，不同优先级的任务可以同时执行。

$3$台服务器的执行时长依次为$1、2、3$。

训练任务的总执行时长为$3$。