You have just been hired as
's personal assistant! In addition to doing his math homework and writing his essays for him, your job description also includes planning out his anime marathons.On this particular day,
Since you want to make
as happy as possible, find the maximum possible happiness he can have if you plan his anime marathon optimally.Constraints
Subtask 1 [20%]
(See Sample Input 1)
Subtask 2 [50%]
(See Sample Input 2)
Subtask 3 [30%]
(See Sample Input 3)
Warning: Fast I/O is highly recommended and even necessary for slower languages such as Java and Python. Check here for details.
Input Specification
The first line of input contains integer
The
Output Specification
One integer, the maximum amount of happiness possible for
if you plan his marathon optimally.Sample Input 1
5
1 2 3
2 1 5
3 1 3
4 2 4
5 1 5
Sample Output 1
13
Explanation for Sample Output 1
If
Sample Input 2
4
1 5 6
1 3 4
1 7 5
4 10 3
Sample Output 2
7
Explanation for Sample Output 2
The optimal plan is to watch animes
Sample Input 3
6
1 1000000000000 1000000000000
99999 99999 99999
123456 789 101112
416647 1333337 1000000000
416647 1 9988776655
99999999999 99999999999 99999999999
Sample Output 3
1000000000000
Explanation for Sample Output 3
Although anime
Comments