J. Bongcloud Opening
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Chess Grandmaster Hikaru Nakamura often plays chess on his favorite website. When a game starts, sometimes Hikaru feels like playing a normal game of chess. But in some cases, to make things a bit interesting and tricky, he plays the Bongcloud opening, which is an atrociously bad way to start a game of chess, but may throw some of his opponents off their game plans.

Today, Hikaru is going to play $$$n$$$ games of chess. Initially, his rating is $$$x$$$. If he defeats his opponent in the $$$i$$$-th game, his rating goes up by $$$a_i$$$ points; if he loses to the $$$i$$$-th opponent, his rating goes down by $$$b_i$$$ points (we assume that draws won't happen at all). The order of Hikaru's opponents cannot be changed. For each opponent, Hikaru knows the result of the game with him even before all the games start, though this result may be different if Hikaru plays Bongcloud instead of a normal game of chess. Formally, for the $$$i$$$-th opponent, two integers $$$c_i$$$ and $$$d_i$$$ are given: $$$c_i = 1$$$ means Hikaru defeats his opponent in a normal game of chess, $$$c_i = 0$$$ means he loses in a normal game; the number $$$d_i$$$ represents the result of the game if Hikaru plays the Bongcloud opening in a same way.

Now, Hikaru has some specific rules to decide whether to start a normal game or a Bongcloud game:

  • if Hikaru's current rating is less than $$$x - k$$$, he plays a normal chess game;
  • if Hikaru's current rating is greater than $$$x + k$$$, he plays with the Bongcloud opening;
  • if none of those two conditions apply, Hikaru can choose either way to play a game.

What is the maximum possible rating Hikaru can achieve after all $$$n$$$ games?

Input

The first line contains three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 2000$$$; $$$0 \le k \le 2$$$; $$$0 \le x \le 10^8$$$).

Then $$$n$$$ lines follow. The $$$i$$$-th line contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ and $$$d_i$$$ ($$$0 \le a_i, b_i \le 10^5$$$; $$$0 \le c_i, d_i \le 1$$$) which describe the $$$i$$$-th opponent.

Output

Print one integer — the maximum rating Hikaru can achieve after all $$$n$$$ games.

Examples
Input
3 2 10
10 2 1 0
6 1 0 1
20 30 1 0
Output
27
Input
2 1 15
10 20 0 0
40 50 0 1
Output
-55
Note

In the first example, Hikaru can obtain the maximum possible rating as follows:

  • in the first game, Hikaru should choose the Bongcloud opening, so he loses, and his rating becomes $$$10 - 2 = 8$$$;
  • in the second game, Hikaru should play normally, so he loses, and his rating becomes $$$8 - 1 = 7$$$;
  • in the third game, Hikaru's rating is lower than $$$10 - 2$$$, so he is forced to play normally; he wins, and his rating becomes $$$7 + 20 = 27$$$.

In the second example, Hikaru loses both games: he loses in the first game no matter how he plays, and his rating becomes $$$-5$$$. Then, his rating is lower than $$$15 - 1$$$, so he is forced to play a normal game of chess, which he loses as well — and his rating becomes $$$-55$$$.