I've been trying to solve this problem from the South America ICPC 2009: https://www.urionlinejudge.com.br/judge/es/problems/view/1412

I am completely stuck and I can't seem to find the solution. It kinda feels like it's some form of DP but I can't seem to find a recurrence that works. Do you have any ideas or hints?

Thank you so much!