我们获得了一家先进的矿石加工设施，据说其目的是“评估 gzip 是否能生产钻石”。该设施将矿石依次通过 $n$ 个阶段进行加工，从粗糙的第一阶段（阶段 1）到最终的阶段 $n$。

每个精炼阶段可以由多台机器组成。每台机器将材料 $i$ 转化为材料 $i + 1$，但它们的效率各不相同，且同一时间只能使用其中一台。机器的规格详细说明了它们消耗多少单位的输入材料，以及生产多少单位的输出材料。

由于仓储成本高昂，所有输入和输出材料都存储在同一个共享仓库中，该仓库的最大容量为 $k$。多余的材料可以随时运出仓库进行处置。

每个阶段必须按顺序进行；一旦某个加工阶段完成，就不能再重新访问。

作为新的运营经理，你的任务是：在给定原材料 1 的初始库存以及有限的仓库容量 $k$ 的情况下，确定可以生产的材料 $n$ 的最大数量。

输入格式

• 第一行包含材料的数量 $n$（$2 \le n \le 30$）和机器的数量 $m$（$n - 1 \le m \le 500$）。
• 第二行包含材料 1 的初始数量 $s$ 和仓库的容量 $k$（$1 \le s \le k \le 10^4$）。

• 接下来 $m$ 行，每行描述一台机器，包含三个整数：

  • $i$（$1 \le i \le n - 1$），输入材料（该机器将材料 $i$ 转化为材料 $i + 1$）。
  • $M_I$（$1 \le M_I \le k$），消耗的材料 $i$ 的数量。
  • $M_O$（$1 \le M_O \le k$），生产的材料 $i + 1$ 的数量。

输出格式

输出一个整数，表示材料 $n$ 的最大最终数量。

样例

输入样例 1

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

输出样例 1

5

输入样例 2

4 4
11 25
1 2 3
1 1 1
2 1 4
3 3 4

输出样例 2

25

输入样例 3

2 2
4 10
1 3 5
1 2 3

输出样例 3

6

输入样例 4

2 1
4 7
1 2 4

输出样例 4

7

输入样例 5

2 1
7 7
1 3 5

输出样例 5

5