В городе Кин-дза-дза на своем пепелаце развозит жителей города единственный на рынке таксист Вазген. Город поделен на 9 районов (с номерами 1-9 соответственно), в каждом из районов 1-8 живет по одному пацаку, каждому из которых необходимо совершить ровно одну поездку в один из прилежащих районов. Пацак из i-ого района зарабатывает i денежных единиц, и готов их все потратить на такси. Вазген без труда может определить, к какому уровню достатка относится каждый из потребителей, поскольку в городе Кин-дза-дза действует правило «цветовой дифференциации штанов»: у каждого пацака разный цвет штанов в зависимости от достатка. Ни один из пацаков не знает, какую цену назначили другим потребителям, поэтому Вазген может выбирать для каждого пацака свою цену (только целую). На перемещение пассажиров Вазген несет издержки на бензин, который закупает как совершенный конкурент в каждом из районов. В i-ом районе сложилось рыночная цена бензина 0,5i за 1 литр. На перемещение между соседними районами Вазген затрачивает 1 литр бензина, а максимальная вместимость его бака равна 3 литрам. В данный момент Вазген находится в 1 районе с пустым баком на заправке. Перемещаться он может исключительно по вертикали и горизонтали в любых направлениях (запрещено перемещаться по диагонали). В конце дня Вазген должен оказаться дома, в 9 районе. Постройте оптимальный маршрут Вазгена с указанием мест заправок, а также найдите его максимальную прибыль, если затраты на бензин – единственные издержки Вазгена.

Расположение районов: квадрат 3*3
1 2 3
4 5 6
7 8 9