题目描述

在回家的路上，九条可怜决定去超市买些东西。她需要买很多东西，但因为是学生，所以她的预算十分有限，最多只能花 $b$ 元。超市一共有 $n$ 种商品。第 $i$ 种商品的价格是 $c_i$ 元。当然，每种商品只能买一次。

最近超市在大促销，作为这家超市的忠实客户，九条可怜收到了 $n$ 张优惠券。如果她购买第 $i$ 种商品，她可以使用第 $i$ 张优惠券将其价格降低 $d_i$ 元。反之如果她不购买相应的商品，就不能使用对应的优惠券。

然而优惠券有一个限制条件：对于所有 $i\ge2$，使用第 $i$ 张优惠劵的同时必须使用第 $x_i$ 张优惠券。

输入格式

第一行两个整数 $n,b$，$1\le n\le 5000$，$1\le b\le 10^9$。

接下来 $n$ 行，描述商品信息。第 $2$ 行描述第一种商品的 $c_i,d_i$，剩下 $n-1$ 行，每行会有第三个信息 $x_i$。

输出格式

输出一个整数表示答案。

6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5

4

5 10
3 1
3 1 1
3 1 2
3 1 3
3 1 4

5