Задача . C. Реформа образования

Недавно в Берляндии была проведена очередная образовательная реформа. Суть ее состоит в следующем.

Теперь учебный год состоит из n дней. Каждый день ученики занимаются ровно одним из m предметов, причем каждому предмету отводится не более одного дня. После завершения занятий по i-ому предмету школьники получают домашнее задание, содержащее не менее a_i и не более b_i упражнений. Кроме того, для каждого предмета определяется специальная характеристика — сложность (c_i). Школа имеет право самостоятельно составлять расписание занятий, однако при этом должны быть выполнены следующие условия:

• предметы в расписании должны располагаться в порядке строгого возрастания сложности;
• каждый день, за исключением первого, задание должно содержать либо в k раз больше, либо на k больше упражнений, чем в предыдущий (более формально: пусть x_i — количество упражнений в домашнем задании в i-ый день, тогда для каждого i (1 < i ≤ n) должно выполняться либо x_i = k + x_i - 1, либо x_i = k·x_i - 1);
• суммарное число упражнений во всех заданиях должно быть максимально возможным.

Все ограничения устанавливаются для каждой школы отдельно.

Оказалось, что a_i и b_i во многих случаях достигают 10¹⁶ (однако, поскольку министр образования Берляндии славится своей любовью к полумерам, величина b_i - a_i не превосходит 100). Случилось так и в Берляндской школе №256. Тем не менее, Вам — как директору этой школы — все равно придется составить расписание для следующего учебного года...