Сложная нестандартная задача

Дано: Игрушка. Прокачка здания. Можно либо купить опыт в размере ровно 1/10 от необходимого до следующего уровня, либо купить улучшение, за которое дадут фиксированное количество опыта. Не делящееся на то, что выше. После получения уровня остаток опыта переносится. Улучшения доступны не раньше определённого уровня. Если просто брать их по мере доступности, то когда они закончатся, останется "хвостик" опыта.

Цель: купить все улучшения так, чтобы лишний опыт был равен нулю или как можно меньше. Таких решений явно больше одного, приоритетным будет такое, в котором улучшения покупаются как можно раньше и ближе к исходному порядку.

Опыта за улучшения: 31250 (ур. 2+), 62500 (ур. 3+), 125000 (ур. 4+), 250000 (ур. 6+), 500000 (ур. 7+), 750000 (ур. 8+), 1250000 (ур. 10+)
Опыта на уровни: 12500 (1->2), 50000 (2->3), 112500, 200000, 312500, 450000, 612500, 800000, 1012500, 1250000, 1512500, 1800000, 2112500, 2450000, ... (макс 20, но туда лезть нет смысла)

Пример того, что нужно сделать - на картинке. Целевая цифра выделена жёлтым. Второй столбец для решения задачи значения не имеет.

Попытался решить перебором в экселе, но не факт, что быстро наткнусь на хотя бы адекватное решение. Тем более что придётся решать задачу больше одного раза. Оптимально написать программу для перебора, но могу потратить на отладку больше времени, чем подобрать вручную - условия хитрые, запутаюсь. Хотя алгоритм прикинул. Даже два.
Решения не жду, хотя бы идеи. Разложить для начала на делители и посмотреть, что получается? Может, задача решаема без тупого подбора, просто я не вижу такого решения? В общем, я пока спать.