Имеется  N городов, соединенных двухсторонними дорогами. Для каждой дороги задана ее протяженность в километрах. Машина может поворачивать (изменять направление движения) только в городах. Машина имеет бак вместимостью Z литров бензина и для нее задан расход бензинаX литров на один километр. В некоторых городах имеются заправочные станции. У каждой  заправочной станции задана своя стоимость 1 литра бензина. В не зависимости от того, сколько бензина осталось в баке машины, на заправке доливается бензин в бак до его полного заполнения. Машина сможет заправиться только в том случае, если ее бак заполнен менее, чем на половину.

      Необходимо определить самый дешевый маршрут из города A в город B, если первоначально бак машины заполнен полностью.