题目描述

学校准备采购若干礼盒。

共有 $n$ 种礼盒，第 $i$ 种礼盒具有唯一编号 $id$、名称 $name$、优先级 $p$、品质分 $q$ 和价格 $c$。

采购前，学校按以下关键字依次排序：

1. 优先级 $p$ 降序；
2. 品质分 $q$ 降序；
3. 价格 $c$ 升序；
4. 名称 $name$ 字典序升序；
5. 编号 $id$ 升序。

只有当前关键字相同时，才比较下一个关键字。

学校初始预算为 $B$，最多采购 $k$ 个礼盒。按照排序后的顺序依次查看每种礼盒：

• 若当前采购数量未达到 $k$ 且剩余预算不少于当前礼盒价格，则采购该礼盒并扣除对应价格；
• 否则跳过该礼盒。

每种礼盒最多采购一次。

输入格式

第一行输入三个整数 $n$、$k$、$B$，相邻整数之间用一个空格分隔。

接下来 $n$ 行，每行输入 $id$、$name$、$p$、$q$、$c$。

其中：

• $name$ 只包含小写英文字母且不含空格；
• 编号两两不同；
• 名称可以相同。

输出格式

第一行输出两个整数：

• 实际采购数量；
• 剩余预算。

第二行输出实际采购礼盒的编号，编号之间用一个空格分隔，顺序与采购顺序一致。

若一个礼盒也未采购，第二行输出 0。

样例

5 3 20
1 apple 2 90 12
2 berry 3 80 15
3 cocoa 3 80 8
4 date 3 80 8
5 elder 1 100 2

3 2
3 4 5

1 1 5
10 alpha 5 90 6

0 5
0

样例解释

样例 $1$ 中，排序后的顺序为 $3、4、2、1、5$。

先采购编号 $3$ 和 $4$，预算剩余 $4$；编号 $2$ 和 $1$ 的价格都超过剩余预算，跳过；最后采购编号 $5$。

实际采购 $3$ 个礼盒，剩余预算为 $2$。

样例 $2$ 中，唯一礼盒的价格超过预算，因此没有采购。

数据范围

$1 \le n \le 100000$。

$1 \le k \le n$。

$0 \le B \le 10^9$。

$1 \le id \le 10^9$。

$1 \le p,q,c \le 10^9$。

名称长度为 $1$ 到 $20$。

所有名称长度之和不超过 $2 \times 10^6$。

预算计算应使用 long long。