Lazy Sorting

Teacher Laur organized a programming contest for his $N$ students and now wants to award them prizes according to their results. The prizes were lined up on a shelf in correct order, but then Toots toppled the shelf with his horseplay. As the prizes are in identical boxes, the teacher put them back on the shelf in a random order.

The prizes have different weights and the teacher has balance scales that he can use to compare two boxes and find out which is intended for the student with the better result. However, each weighing takes time and the first $M$ students have already lined up behind his door to receive their prizes...

To minimize the total time that students spend waiting for their prizes, the teacher wants to give each student their prize with as few weighings as possible. Write a program to help the teacher do that.