Writing

Hiring Pizza Chefs

Taki has finally decided to hire employees. In fact, he has found ~N~ candidate pizza chefs. Each candidate can be hired under at most one type of contract: bronze, silver, or gold. Taki's budget allows him to offer up to ~X~ bronze contracts, up to ~Y~ silver contracts, and up to ~Z~ gold contracts. Furthermore, he has made sure that ~X + Y + Z \ge N~.

A pizza chef's performance depends on the contract they receive. If the ~i~-th pizza chef is offered a bronze contract, their performance will be ~A_i~; if they are offered a silver contract, it will be ~B_i~; and if they are offered a gold contract, it will be ~C_i~. For all candidates, ~A_i \le B_i \le C_i~, meaning that offering a higher-tier contract always improves their performance.

Naturally, Taki wants to maximize the total performance of his pizza chefs, that is, the sum of their individual performances. However, he must stay within his budget. Find the maximum total performance Taki can achieve while respecting the limits he has set for each type of contract.

Problem

Write a program in one of the OJDP (PASCAL, C, C++, JAVA) programming languages that reads the input data from the file hiring.in and prints the results to the file hiring.out.

Input Files (hiring.in)

The first line contains the subtask number (see below). The second line contains four integers ~N~, ~X~, ~Y~, and ~Z~, separated by spaces: the number of candidates, the maximum number of bronze contracts, the maximum number of silver contracts, and the maximum number of gold contracts. The next ~N~ lines each contain three integers ~A_i~, ~B_i~, and ~C_i~, separated by spaces: the performance of the ~i~-th candidate if they are offered a bronze, silver, or gold contract, respectively.

Output Files (hiring.out)

It must contain a single line with an integer: the maximum total performance Taki can achieve by offering at most ~X~ bronze contracts, at most ~Y~ silver contracts, and at most ~Z~ gold contracts.

Sample input - output files:

Input:

1
5 3 1 1
3 6 8
1 1 2
4 9 12
3 5 7
9 9 9

Output:

31

Explanation: The best choice is to give a silver contract to the first candidate (performance ~6~), a bronze contract to the second (performance ~1~), a gold contract to the third (performance ~12~), a bronze contract to the fourth (performance ~3~), and a bronze contract to the fifth (performance ~9~). The total performance is therefore ~6 + 1 + 12 + 3 + 9 = 31~.

Subtasks:

1. (8 points) ~N \le 14~
2. (24 points) ~Z = 0~
3. (3 points) ~X = 0~
4. (12 points) ~A_1 = A_2 = ... = A_N~ (the performance values for bronze contracts are all equal), ~B_1 \le B_2 \le ... \le B_N~ (the performance values for silver contracts are in non-decreasing order), and ~C_1 \ge C_2 \ge ... \ge C_N~ (the performance values for gold contracts are in non-increasing order)
5. (20 points) ~Z = 1~
6. (33 points) There are no further constraints

Constraints

• ~1 \le N \le 100.000~
• ~0 \le X,; Y,; Z \le N~
• ~X + Y + Z \ge N~
• ~1 \le A_i \le B_i \le C_i \le 1.000.000.000~

Notes

• Formatting: In both the input and the output, each line ends with a newline character.
• Maximum execution time: ~1~ sec.
• Maximum available memory: ~64~ MB.
• Source code headers: At the beginning of your source code, you must use the following headers.

(* USER: username
LANG: PASCAL
TASK: hiring *)

for PASCAL code

/* USER: username
LANG: C
TASK: hiring */

for C code

/* USER: username
LANG: C++
TASK: hiring */

for C++ code

/* USER: username
LANG: Java
TASK: hiring */

for Java code

Warning: The answer may exceed ~2^{32}~. Also, make sure to read the input and print the output efficiently, especially if you are translating to C++ or Java.