超能侠在执行任务时遇到了一个惊险的场景，他被困在一个名为“能量井”的地方，这个井的深度为 D。在能量井中，他可以吸取周围的能量来维持生命，或利用周围的能量搭建能量梯来逃离这个井。

能量井中的能量不是随时都有的，为了制定详细的逃亡计划，超能侠事先得知了每波能量的相关信息。井中一共会涌现G波能量，他已经知道了每波能量的出现时间t，吸取这波能量能够维持生命的时间 f（单位均为小时），以及能够用这波能量搭建的能量梯高度h。

目前超能侠体内还拥有维持 10 小时的生命所需的能量。如果太久没有吸取能量或直到最后也没有搭建出足够高的能量梯，超能侠将会在此陨落。

请帮助超能侠制定逃亡计划，如果他可以逃出能量井，则输出最早能够逃离能量井的时间；如果他无法逃离，则输出他最长可以存活多长时间。

输入文件第一行为用一个空格隔开的两个整数D,G，分别代表井的高度和能量的波数。

之后G行，每行三个整数，分别表示第i波能量的出现时间ti，吸取这波能量能够维持生命的时间 fi，以及能够用这波能量搭建的能量梯高度hi。不保证输入按时间顺序排列。

输出文件仅有一行。如果超能侠可以逃出能量井，则输出最早能够逃离能量井的时间；如果他无法逃离，则先输出-1，再输出他最长可以存活多长时间，用空格隔开。

【输入输出样例1说明】

第5小时，超能侠得到了第一波能量，他用这波能量建造了高为9的能量梯，目前能量梯高为9；

第9小时，超能侠得到了第二波能量，他吸取了能量，延长了3小时的生命，现在他可以存活到第13小时；

第12小时，超能侠得到了第三波能量，他用这波能量建造了高为10的能量梯，目前能量梯高为10；

第13小时，超能侠得到了第四波能量，他用这波能量建造了高为1的能量梯，目前能量梯高为20，超能侠在第13小时成功逃出。

对于100%的数据，保证 20≤D≤100, 1≤G≤100, 1≤t≤1000，1≤f≤30,1≤h≤15。