I was trying to solve this problem form recent Atcoder's beginner contest , but after scratching my head for almost 2h I could not come up with the solution.Then I tried to look for the editorials but this time they were not in English. square1001 has provided solution there which I find uses some kind of DP. Can anyone who has solved this problem explain DP recurrence behind this ?