23831번 - 나 퇴사임?

SASA의 자습 시간에는 매일마다 정독실, 소학습실, 휴게실, 그리고 방에서 휴식을 취할 수 있는 요양 4가지 중 하나를 선택할 수 있다.

우석이는 자습 장소에 따라 얻을 수 있는 만족도가 있으며, 그 4가지 값은 매일 우석이의 기분에 따라 결정된다.

우석이는 자습을 총 $N$일 동안 해야 하며, 기숙사에는 다음과 같은 규칙이 있다.

• 요양 신청은 최대 $A$회 가능하다.
• 휴게실에서 이틀 연속으로 자습을 할 경우, 게임을 하는 것으로 판단되어 퇴사 처리된다.
• 정독실이나 소학습실에서 자습을 총 $B$회 미만으로 할 경우, 학습 의지 상실로 판단되어 퇴사 처리된다.

공부하기 싫은 우석이가 퇴사를 당하지 않고 기숙사의 규칙을 지키면서 $N$일 동안 얻을 수 있는 만족도의 합의 최댓값을 구해보자.

첫째 줄에 자습일의 수 $N$이 주어진다.

둘째 줄에 가능한 요양 신청 횟수 $A$와 정독실과 소학습실에서 합쳐서 필수적으로 자습을 해야 하는 횟수 $B$가 주어진다.

셋째 줄부터 $N$ 개의 줄의 $i$ 번째 줄에는 4개의 정수 $p_i, q_i, r_i, s_i$가 공백으로 구분되어 주어진다. 이 값은 $i$번째 자습일에 정독실, 소학습실, 휴게실 자습 및 요양을 할 때 얻는 만족도를 의미한다.

기숙사의 규칙을 지키면서 $N$일 동안 얻을 수 있는 만족도의 합의 최댓값을 출력한다.

• $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$