Nice.

btw, can any body solve the Problem D in Contest #6 if the constraints are not reduced? During the contest, I can only get a lot of fast and wrong greedy strategies and a definitely TLEed DP.