Задача . B. Лемминги

Как известно, лемминги любят прыгать. Для очередного эффектного группового прыжка n леммингов собрались у высокой скалы, на которой расположены k удобных уступов. Первый уступ расположен на высоте h метров, второй — на высоте 2h, и так далее (i-ый на высоте i·h метров). Лемминги собираются прыгать на закате, до которого осталось не так много времени.

Каждый лемминг характеризуется скоростью подъёма v_i метров в минуту и массой m_i. Это означает, что i-й лемминг может взобраться на j-й уступ за время минут.

Чтобы прыжок получился красивым, более тяжелые лемминги должны прыгать с более высоких уступов: если лемминг массой m_i прыгает с уступа i, а лемминг массой m_j прыгает с уступа j (для i < j), то должно выполняться неравенство m_i ≤ m_j.

Так как леммингов n, а уступов всего k (k ≤ n), то из n леммингов предстоит выбрать k, которые примут участие в прыжке. Выбранных леммингов нужно распределить по уступам с 1 по k по одному леммингу на уступ. Лемминги должны быть упорядочены в порядке неубывания массы с возрастанием высоты уступа. Кроме того, каждый лемминг должен успеть подняться на свой уступ, то есть время его подъёма не должно превышать t минут. Лемминги карабкаются на свои уступы все одновременно и не мешают друг другу.

Определите способ организовать прыжок леммингов таким образом, чтобы время t было минимально.