Chef and Direction

Chef has opened new restaurant "Direction" and his first problem is to find cooks. Chef has K candidates, each of them is characterized by P[i] and S[i] - the number of dishes that he can cook per minute and the salary he wants, cook gets salary only once. Two cooks can't work on the one order together, but every cook whenever he wants can interrupt another cook and start working on his order, eve