Score : 400 points
There are N pieces of sushi. Each piece has two parameters: "kind of topping" t_i and "deliciousness" d_i. You are choosing K among these N pieces to eat. Your "satisfaction" here will be calculated as follows:
You want to have as much satisfaction as possible. Find this maximum satisfaction.
Input is given from Standard Input in the following format:
N K t_1 d_1 t_2 d_2 . . . t_N d_N
Print the maximum satisfaction that you can obtain.
5 3 1 9 1 7 2 6 2 5 3 1
26
If you eat Sushi 1,2 and 3:
Thus, your satisfaction will be 26, which is optimal.
7 4 1 1 2 1 3 1 4 6 4 5 4 5 4 5
25
It is optimal to eat Sushi 1,2,3 and 4.
6 5 5 1000000000 2 990000000 3 980000000 6 970000000 6 960000000 4 950000000
4900000016
Note that the output may not fit into a 32-bit integer type.