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:
What is the maximum possible rating Hikaru can achieve after all $$$n$$$ games?
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.
Print one integer — the maximum rating Hikaru can achieve after all $$$n$$$ games.
3 2 10 10 2 1 0 6 1 0 1 20 30 1 0
27
2 1 15 10 20 0 0 40 50 0 1
-55
In the first example, Hikaru can obtain the maximum possible rating as follows:
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$$$.
Name |
---|