This is painful problem, I spent 3 hours to solve, but very educational actually. If you are struggling, than read this: https://codeforces.com/topic/60789/ru9