If you have WA15 use for dp and for fees long long, because not optimal answer for official, which can be before program find optimal answer, may be more then 10^9.