该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

文文最近陷入了自由和爱情的选择，但是选择爱情会失去一部分自由，选择自由又会失去爱情。

仅仅选择是不够的，有句古话说的好“钱不是万能的，但没有钱是万万不能的”，文文身上只有i块钱，下列有 $N$ 种情况，每种情况只能发生一次，每种情况有 $X,Y,Z$ 三个值，$X$ 代表自由或爱情，$Y$ 代表这种情况需要花费的钱，$Z$ 代表这种情况带给你的价值。（若是选择了爱情就不能选择自由）

文文希望你告诉他选择自由还是爱情(由于文文更希望是自由，所以当爱情和自由的最高价值相同时选择自由），并且能获得的最高价值是多少

输入格式

第一行有两个整数 $N,i(1 ≤ N ≤ 20,1 ≤ i ≤100)$，用空格隔开，分别表示情况次数和所拥有的钱。

接下来有 $N$ 种情况：

每行有三个整数 $X,Y,Z (0 ≤ X ≤ 1,0 < Y,Z ≤ 100)$，用空格隔开，$X$ 代表自由或爱情(0 是自由，1 是爱情），$Y$ 代表这种情况需要花费的钱，$Z$ 代表价值。

输出格式

输出两个整数，表示最大价值和他对应的选择。

3 5
0 2 3
1 4 7
0 3 5

8 0