Hello, could someone help me to solve the following problem?
A conversation time consists of N parts. Each of first N-1 parts last for K[i] minutes, the N-th part is considered to be infinite. Each minute of a part i costs E[i]. Parts are consecutive, i.e. part N+1 always goes right after the end of part N. The pay is per-minute (you pay at the beginning of a new minute for entire minute). If you have no enough money for a new minute, the conversation is interrupted.
You are given integers N and M. N-1 integers K[i] and N integers E[i]. The task is to find the maximal possible number of minutes that you can speak over the telephone (it is possible to make several calls).
1 <= N <= 77,
1 <= M, K[i], E[i] <= 1000000 (10^6)
time: 5 sec
memory: 64 mb