After praying to the rating gods of Codeforces and Mr. DeMello, they have granted you the ability to view your future contest deltas.

For every contest, you can choose to either take or not take it, but these choices affect future contests.

Specifically, you can take the contest and travel to node $v$ to gain $D$ rating, or not take the contest and travel to node $w$ to maintain your current rating.

You are initially at node $1$.

A node represents the state of contests that you have taken in the past.

Since this is your rating, you decide to find the maximum rating you can achieve after you have made a choice for each contest.

Can you help yourself?

Input Specification

The first line will contain $N$ $(1\le N\le 17)$ and $R$ $(0\le R\le 1000000000)$, the number of contests and your current rating.

The next $2^N-1$ lines will contain $u$, $v$, and $w$ $(1\le u,v,w\le 2^{N+1}-1,u\ne v\ne w)$, then $D$ $(-10000\le D\le 10000)$, the current node, the next node if you take the contest, the next node if you do not take the contest, and the rating change if you take the contest.

Note: The data guarantee that the connections cannot return to an earlier contest and form a directed tree.

Output Specification

Output the maximum rating achievable.

Sample Input

3 1500
1 2 3 500
2 4 5 700
3 6 7 -500
4 8 9 100
5 10 11 50
6 12 13 1000
7 14 15 50

Sample Output

2800

Explanation for Sample Output

The maximum achievable rating is $2800$. To achieve this, you can take the first contest $(+500)$, take the second contest $(+700)$, and take the third contest $(+100)$.