题目描述

新年必不可少的就是串门啦。@zls_XICK 提上包好的饺子准备出门，但是先去串谁家门又成了个问题，他便回到桌上打算列一个串门对象的名单。

@zls_XICK 有 $N$ 位朋友今天有空，可以去他们家串门，由于有的朋友比较内向，说的话比较少，所以串门所要花费的时间就比较少，而朋友也会回礼，第 $i$ 位朋友串门所需单位时间为 $t_i$，回礼的价值为 $v_i$，名字为 $S_i$。但是 @zls_XICK 今天时间有限，只有 $M$ 单位时间，现在他要列出能获得的最高礼物总价值和其对应的方案串门对象名单：

• 名单按所给礼物价值从大到小排序，礼物价值相同则按其名字字典序排序。

• 若有多个方案可获得的礼物总价值相同，选择按上述规则排序后的整体名单内，人数最少的方案，若人数仍相同，选择名单最后一位在排序后整体名单最靠前的方案，相同则比较前一位。

输入格式

输入包括 $N + 1$ 行。

第一行 $2$ 个整数 $N$、$M$，含义如题意所示。

随后 $N$ 行，每行 $2$ 个整数 $t_i$、$v_i$ 和一个长度不超过 $10^3$ 的字符串 $S_i$，表示第 $i$ 位朋友串门所需时间、回礼的价值、名字。

输出格式

输出包括 $2$ 行。

第一行一个整数表示可获得的最大礼物总价值。

第二行若干个字符串，表示串门对象名单，每两个字符串间用空格隔开

6 10
3 2 Dw2025
4 3 Lelzy
5 5 mywwzh
4 4 Genius_star
6 4 Xlw6friend
5 3 _Cby_

9
mywwzh Genius_star

数据规模与约定

对于 $40 \%$ 的数据满足 $1 \le N,M \le 20$。

对于 $100 \%$ 的数据满足 $1 \le N \le 10^3$，$1 \le t_i \le M \le 10^3$，$1 \le S_i.size() \le 10^3$。