Under construction

Still being built. Things may change

Writing Jutae's Personal Statement

Time limit1sMemory limit256 MB

Summary
Assign each story to at most one of three questions, with per-question caps and at least one story each, to maximize total fit score.
Level

Medium7 of 10

Topics
Graph, Shortest path, Greedy
Solved
No attempts yet

Problem

Jutae has started writing a college application essay with three questions. Jutae has a wide range of school life stories, but learned that using too many stories can count against the essay. So Jutae decided to compute the fit between each story and each question, then pick which stories to use. Jutae needs a break after computing the fit scores, so choosing the stories is up to you. Find the largest total fit Jutae can get. Each question must contain at least one story, and no story may be used more than once.

Input

The first line contains the number of stories N (3 ≤ N ≤ 500). The second line contains the maximum number of stories that can go into each question, A, B, and C (1 ≤ A, B, C ≤ N), in that order. Each of the next N lines contains the fit a, b, and c (-10,000 ≤ a, b, c ≤ 10,000) of the i-th story with each question, in order. All input values are integers.

Output

Print the largest total fit Jutae can get.

Examples2

  1. Example 1

    Input
    4
1 1 1
60 50 100
30 20 90
10 6 33
1 25 80
    Expected output
    175

  2. Example 2

    Input
    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
    Expected output
    43