시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 64 26 13 32.500%

문제

이제 고 3이 되는 주때는 문항 수가 3개인 대입 자기소개서를 쓰기 시작했다. 학교생활의 스토리가 방대한 주때는 다양한 스토리를 뽑아냈지만 너무 많은 스토리를 쓰면 마이너스 요소가 될 수 있다는 것을 깨달았고, 주때는 스토리와 각 문항과의 적합성을 구해놓고 선택하기로 마음먹었다. 적합성을 구해놓은 주때는 휴식이 필요했고, 스토리를 정하는 것은 당신에게 맡기기로 했다. 주때를 위해 얻을 수 있는 가장 큰 적합성을 구해주자! 각 문항에는 한 개 이상의 스토리가 들어가야 하며 스토리를 중복해서 사용할 수 없다.

입력

첫 번째 줄에는 스토리의 개수 N(3 ≤ N ≤ 500)이 주어진다.

다음 줄에는 각 문항의 들어갈 수 있는 최대 스토리의 개수 A, B, C (1 ≤ A, B, C ≤ N)가 순서대로 주어진다.

다음 N개 줄의 i번째 줄에는 i번째 스토리와 각 문항과의 적합성 a, b, c (-10,000 ≤ a, b, c ≤ 10,000)가 순서대로 주어진다.

입력은 모두 정수로 주어진다.

출력

주때가 얻을 수 있는 가장 많은 적합성을 출력한다.

예제 입력 1

4
1 1 1
60 50 100
30 20 90
10 6 33
1 25 80

예제 출력 1

175

예제 입력 2

7
1 5 6
1 -4 2
3 7 -3
-9 -10 -4
9 -5 9
-8 7 -4
9 1 -1
0 3 9

예제 출력 2

43

출처