当前没有测试数据。

Background

Special for beginners, ^_^

Description

徐老师去外地调研加旅游了，已知早上吃早饭的总时间为T，早晨宾馆给他提供丰富的自助早餐，共有N种食物，对于每种食物，他可以有三种选择：

1. 不吃，不花时间，当然，得到的营养价值也是0；
2. 站着狼吞虎咽吃，花费时间为T1，得到的营养价值为W1；
3. 放到盘子里，端到座位上慢慢吃，花费时间为T2，得到的营养价值为W2。

请你求出在规定的时间内，徐老师能获得的最大营养价值。

Format

Input

第一行，两个整数：N，T。 接下来N行，每行四个整数，分别是T1，W1，T2，W2

Output

一个整数，最大营养价值。

Samples

3 10
2 4 3 2
3 3 6 1
5 8 4 2

15

Limitation

1s, 1024KiB for each test case.