问题描述

WW合成了很多漂亮的锂矿石，并把它们存放到了仓库中。由于锂矿石身价不菲，各路蟊贼大盗都开始蠢蠢欲动。为了保护自己的合法私有财产，WW决定花n元钱聘请一些本领高强的护卫。招聘告示发出后，应聘的专业护卫蜂拥而至，他们之间的实力差距很大。 如何才能用有限的钱请到最合格的护卫呢？这是一个很严肃的问题！为了不浪费每一分钱，WW慕名找到了你，委托你来为他分忧，并承诺事后送你一块锂矿石......

输入文件

第一行两个整数n，m，分别表示要花的钱和应聘的人数 从第二行到第m+1行，每行开头一个由大写字母和数字组成的字符串（长度小于50），表示标号为i的护卫的名字，空格后跟两个整数w[i],v[i],分别表示标号为i的护卫要求的薪水以及他的能力值

输出文件

第一行一个整数表示所聘请的护卫的能力值之和

以下若干行，每行一个字符串，分别表示选中的护卫的名字，按照他们在输入中给出的顺序输出（如果出现若干个不同的护卫，且都能使最终所聘请的护卫的能力值之和达到最大，则聘用标号大的护卫）。

样例输入

70 3
XX 71 100
W1W 69 1
ZZ 1 2

样例输出

3
W1W
ZZ

数据范围

对于全部数据，0<=n<=1000,0<=m<=100，1<=w[i]，v[i]<=200