Благодаря помощи Доктора, повстанцам удалось украсть достаточно золота, чтобы запустить полномасштабную атаку на эмперию! Однако Дарт Вейдер ищет возможности отомстить и забрать назад своё золото.
Повстанцы спрятали золото на различных базах по всей галактике. Дарт Вейдер и Империя собираются послать свои космические корабли в атаку на эти базы.
Галактика может быть представлена как неориентированный граф из \(n\) планет (вершин) и \(m\) червоточин (рёбер), каждая соединяющая две планеты.
Всего у империи есть \(s\) космических кораблей, а у повстанцев есть \(b\) баз, расположенных на различных планетах галактики.
У каждого космического корабля есть его местоположение \(x\), обозначающее индекс планеты, на которой он находится, его сила атаки \(a\) и определённый уровень топлива \(f\).
У каждой базы есть местоположение \(x\) и уровень защиты \(d\).
Космический корабль может атаковать базу если выполнены оба следующих условия:
- Сила атаки космического корабля больше или равна уровня защиты базы,
- Уровень топлива космического корабля больше или равен кратчайшему расстоянию (количество червоточин) между планетой космического корабля и планетой с базой
Вейдер очень требователен к своим атакующим формациям. Он требует, чтобы каждый космический корабль атаковал не более одной базы, и чтобы каждая база была атакована не более чем одним космическим кораблем.
Вейдер знает, что повстанцы спрятали \(k\) золота в каждой базе, так что он назначит космическим кораблям базы для атаки таким образом, чтобы максимизировать число атакованных баз.
Таким образом, для каждой атакованной базы повстанцы теряют по \(k\) золота.
Однако повстанцы имеют возможность создать произвольное количество фейковых баз. С помощью Доктора, эти базы будут существовать за пределами пространства и времени, так что все корабли смогут достичь и атаковать их. Более того, фейковые базы всегда будут казаться очень заманчивыми, то есть они гарантировано будут атакованы каким-то кораблём.
Разумеется, фейковые базы не содержат золота, но создание одной такой базы стоит \(h\) золота.
Какое минимальное количество золота повстанцы потеряют, если они создадут оптимальное количество фейковых баз?