说明

U蒟蒻学不懂dp，也做不来背包，他只会打游戏。

“警告！致命错误：系统完整性严重损坏……”

这是一场威胁人形存亡的空前危机，面对强劲的敌人和未知的前路，散落各地的人形小姐姐们正凭各自的意志咬牙挣扎，寻求渺茫的希望。尽管人类已决定放弃他们，身为“云图计划”负责人的您，义无反顾踏入了这片未知的土地，集结人形并建立“流亡者”队伍，成为他们的领导者，探索这个世界的秘密，找寻脱离绝境的方法，揭开事件背后的真相……各具职业特色的次世代人形等待您下达指令。小U目前只收集了n个人形小姐姐。搜寻他们的身影，扩大“流亡者”队伍的规模，多元化培养您中意的人形们，这n个小姐姐中有小U喜欢的，也有小U不是很喜欢的，如果一个人形小姐姐让小U很喜欢就会给她送她喜欢的礼物，以此提高她的好感度w。辅助他们突破心智枷锁的束缚，甚至发掘他们不为人知的过去——嘘，这是只属于你们彼此之间的秘密。最近新出的游戏“云图计划”里有很多好看的小姐姐，每一个小姐姐的战斗力都不一样。今天凌晨4：25的时候小U在打一个推荐战力为x的副本，但是他不想队伍的总战斗力超过x，他喜欢通过他精湛的决策来通关这个副本。他想编出他最喜欢的一个队伍来打这个副本，善良的你可以帮帮他吗？

输入格式

第一行有两个整数x，n。

接下来的n行每行有一个字符串以及两个整数，分别代表小姐姐的名字，小姐姐的战斗力和她的好感度。

输出格式

输出小U最喜欢的一个队伍（将小姐姐的名字按照战力从大到小输出，名字之间需换行分隔），输完所有名字后换行输出总好感度。

样例

29000 9
帕斯卡 5479 8
缠枝 6364 11
克罗琦 4289 9
琴 4949 9
薇 3988 9
坂口希 2773 9
秋 6042 11
芙洛伦 2098 7
咲耶 1622 7

缠枝
秋
琴
克罗琦
坂口希
芙洛伦
咲耶
63

提示

数据范围：

0<x<50000；

0<n<50；

0<w<15