Problem I
Incinerating Incantations

Ivar is an experienced mage and want to help his community celebrating Saint John’s Eve. They want a big bonfire, and with his spells, he can help them make the bonfire even bigger. Ivar has in total $N$ spells he can cast, but can only cast each spell at most once. Additionally, he only has $M$ mana, so he may not be able to cast all the spells he knows.

And the spells are complicated and tedious to work with. They affect many different things – including future spells you may want to cast. More specifically, when casting a spell $i$, the following happens in this exact order:

1. It consumes $m_i$ mana (Ivar can’t cast it if he does not have enough mana)

2. It increases the fire power by $f_i$

3. It increases the mana cost of the next spell cast by $m^{next}_i$

4. It increases the mana cost of all following spells cast by $m^{all}_i$

5. It increases the fire power of the next spell cast by $f^{next}_i$

6. It increases the fire power of all following spells cast by $f^{all}_i$

Of course, the cost of a spell cannot go negative: If a spell costs $1$ mana to cast and is reduced by $2$ (i.e. increased by $-2$), it will cost $0$ mana to cast, not give you back $1$ mana when casting. Similarly, the fire power of a spell cannot go negative either.

Ivar isn’t entirely sure which order he should cast his spells however, and he’s come to you to get some help on the matter. Can you help Ivar find out how much additional fire power he can add to the bonfire, if he optimally chooses which spells to cast, and in what order?

Input

The first line contains two integers $N$ and $M$, specifying the total number of spells Ivar knows, and his current mana. Then follow $N$ lines, specifying a spell. Each spell line contain $6$ integers $m_i$, $f_i$, $m^{next}_i$, $m^{all}_i$, $f^{next}_i$, and $f^{all}_i$, as described above.

Output

Output the most fire power Ivar can emit.

Limits

• $0 < N \leq 9$

• $0 \leq M \leq 100$

• $0 \leq m_i, f_i \leq 200$

• $-200 \leq m^{next}_i, m^{all}_i, f^{next}_i, f^{all}_i \leq 200$

3 3
10 10 0 0 0 0
1 0 -3 -3 -10 -2
7 4 -8 0 0 -2

6

5 3
0 0 0 0 0 0
10 0 0 1 1 3
0 0 0 0 0 0
0 0 -8 -1 0 -100
0 0 0 0 0 0

7