Hi codeforces.

My coach gave me a problem the other day and I'm still stuck in it and I have no idea on how to solve it.

I was wondering if you could help me.

It goes like this:

You are in a candy workshop you have N candies , M boxes with the capacity of C units and each candy has it's own wight.

The candies are in a production line so you can't rearrange them you are standing in the front of the line and you have to bag as many candies as you can.

When a candy piece arrives to you , you have 3 choices

1) take the candy and subtract it's wight from the remaining wight of the box ( as long as it's wight is less or equal to the box's remaining wight)

2) discard the candy( NOTE : that you can not take the candy again )

3) close the box you have and open a new one ( if you have a box left )

What is the maximum number of candies you can bag in the boxes.

NOTE : that you stand in the left of the production line.

1 <= N <= 1000000 1 <= M,C <= 1000000

e.g:

N = 8

M = 2

C = 20

The candies are 12 8 5 10 13 15 4 7

The output is : 5

You can take 12 and 8 and put them in the first box and close it then you can take 5 and 10 and 4 and you're done.

e.g2:

N = 24

M = 1

C = 20

The candies are 13 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 13

The output is : 20