Statement

In the middle of the night Luca has been attacked by bugs, which are very well organised and form a line in front of his bed. In order to protect himself, Luca has K slippers to be thrown at the bugs one at a time (but optionally he can throw multiple slippers at the same bug). The bugs, being very creative, are playing dead to fool him: the room is dark and he can only barely see the bugs, without knowing which ones are squashed and which are alive. Fortunately, Luca knows that the i-th bug in the line of N bugs has a probability P_i to be squashed when he throws a slipper at it. That probability does not change, meaning that subsequent slippers also have a probability P_i to kill it, if it is not already killed. Luca is very tired and hates bugs crawling around in his room in the middle of the night. Help him use the slippers in the wisest way possible, in order to maximize the expected number of killed bugs.