This code uses a round of backtracking greed and local dynamic programming.

It can be hacked by this data.

data.in
10 24
1 10001
1 10001
3 30000
3 30000
3 30000
3 30000
3 30000
3 30000
3 30000
3 30000

data.out
240000

user.out
230002

If Tourist (rating>=4000) uses magic on his account, can he change it back?