Am I Fired?

During SASA's self-study time, each day you can choose one of four options: the reading room, the small study room, the lounge, and resting in your room (recuperation).

Wooseok gets a satisfaction value from each self-study location, and these four values are determined each day by Wooseok's mood.

Wooseok must do self-study for a total of $N$ days, and the dormitory has the following rules.

• Recuperation may be requested at most $A$ times.
• If he studies in the lounge on two consecutive days, it is judged that he is playing games and he is fired.
• If he studies in the reading room or the small study room fewer than $B$ times in total, it is judged that he has lost the will to learn and he is fired.

Wooseok hates studying. Find the maximum possible sum of satisfaction over $N$ days such that he is not fired and obeys the dormitory rules.

The first line gives the number of self-study days $N$.

The second line gives the maximum number of recuperation requests $A$ and the number of times $B$ that he must necessarily study in the reading room and the small study room combined.

From the third line, the $i$-th of $N$ lines gives four integers $p_i, q_i, r_i, s_i$ separated by spaces. These values are the satisfaction obtained on the $i$-th self-study day from studying in the reading room, studying in the small study room, studying in the lounge, and recuperation.

Print the maximum possible sum of satisfaction over $N$ days such that he obeys the dormitory rules.

• $1 \leq N \leq 100$
• $0 \leq A, B \leq N$
• $1 \leq p_i, q_i \leq r_i \leq s_i \leq 100$