f (city, subset, discount) = min cost
   50    2^7     71
         128     0%--70%
Рёбра: пойти по графу (всего 500 рёбер, <= 50 из вершины)
       или купить одну вещь (<= 7 рёбер)

Динамика? Но мы не знаем порядок, в котором нужно рассматривать состояния!
Порядок: алгоритм Дейкстры.