| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 128 | 61 | 49 | 44.954% |
There are $N$ beavers in JOI University. All of them are working on competitive programming. Each beaver has three abilities: consideration skill, implementation skill, and luck. If the value of an ability is large, it means the level of the ability is high. For each $i$ (1ドル ≤ i ≤ N$), the consideration skill of the beaver $i$ is $X_i,ドル the implementation skill of the beaver $i$ is $Y_i,ドル and the luck of the beaver $i$ is $Z_i$.
This year, the beavers of JOI University will attend a programming contest for teams. In this contest, the participants solve programming tasks, and each team consists of three beavers. Bitaro is a coach of JOI University. Since teamwork is very important, Bitaro decided to choose three beavers among the $N$ beavers and make a team so that the following condition is satisfied.
Condition Every member in the team has an advantage. This means every member has an ability whose value is strictly larger than the values of the same ability of the other two members.
Among possible teams satisfying the above condition, Bitaro wants to choose a team whose total ability is as large as possible. Here, the total ability of a team is defined as the sum of the maximum value of the consideration skill of the members of the team, the maximum value of the implementation skill of the members of the team, and the maximum value of the luck of the members of the team.
Write a program which, given information of the abilities of each beaver, determines whether it is possible to make a team satisfying the above condition, and, if it is possible to make a team, calculate the maximum possible value of the total ability of a team.
Read the following data from the standard input. Given values are all integers.
$\begin{align*} & N \\ & X_1 ,円 Y_1 ,円 Z_1 \\ & X_2 ,円 Y_2 ,円 Z_2 \\ & \vdots \\ & X_N ,円 Y_N ,円 Z_N \end{align*}$
Write one line to the standard output. The output should contain the maximum possible value of the total ability of a team. If it is impossible to make a team satisfying the condition, output -1.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $N ≤ 300$. |
| 2 | 29 | $N ≤ 4,000円$. |
| 3 | 9 | $X_i ≤ 5,ドル $Y_i ≤ 5,ドル $Z_i ≤ 5$ (1ドル ≤ i ≤ N$). |
| 4 | 9 | $X_i ≤ 20,ドル $Y_i ≤ 20,ドル $Z_i ≤ 20$ (1ドル ≤ i ≤ N$). |
| 5 | 9 | $X_i ≤ 300,ドル $Y_i ≤ 300,ドル $Z_i ≤ 300$ (1ドル ≤ i ≤ N$). |
| 6 | 9 | $X_i ≤ 4,000円,ドル $Y_i ≤ 4,000円,ドル $Z_i ≤ 4,000円$ (1ドル ≤ i ≤ N$). |
| 7 | 27 | No additional constraints. |
5 3 1 4 2 3 1 1 5 5 4 4 2 5 2 3
13
If we make a team consisting of the beaver 1ドル,ドル the beaver 4,ドル and the beaver 5ドル,ドル the condition of the task is satisfied.
Then, the maximum values of the consideration skill, implementation skill, luck of the members of the team are 5ドル,ドル 4ドル,ドル 4ドル,ドル respectively. The total ability of the team is 13ドル$. Since it is impossible to make a team whose total ability is larger than or equal to 14ドル,ドル output 13ドル$.
Note that if we make a team consisting of the beaver 1ドル,ドル the beaver 3ドル,ドル and the beaver 5ドル,ドル the total ability becomes 15ドル$. However, since the beaver 1ドル$ does not have an ability whose value is strictly larger than the values of the same ability of the other two members, the condition of the task is not satisfied.
This sample input satisfies the constraints of all the subtasks.
8 1 1 1 1 1 5 1 5 1 5 1 1 1 5 5 5 1 5 5 5 1 5 5 5
15
If we make a team consisting of the beaver 2ドル,ドル the beaver 3ドル,ドル and the beaver 4ドル,ドル the total ability of the team is 15ドル$. Since it is impossible to make a team whose total ability is larger than or equal to 16ドル,ドル output 15ドル$.
This sample input satisfies the constraints of all the subtasks.
4 1 2 3 1 2 3 1 2 3 1 2 3
-1
Since it is impossible to make a team satisfying the condition of the task, output -1.
This sample input satisfies the constraints of all the subtasks.
Camp > JOI Spring Training Camp > JOI 2021/2022 Spring Training Camp 2-3번
Camp > JOIG Spring Training Camp > JOIG 2021/2022 Spring Training Camp 1-3번