Інгредієнти

Шеф-кухар ресторану, який прагне отримати зірку Мішлен, хоче вразити інспекторів, представивши їм вибір своїх фірмових страв. Для цього вона виділила максимальний бюджет $B$ на загальну вартість і прагне максимізувати загальний престиж страв, які будуть показані інспекторам.

Щоб оцінити престиж своїх страв, шеф-кухар складає список рецептів, вказуючи їхню вартість та інгредієнти. Кожен рецепт описує, як отримати похідну страву з базової, додаючи інгредієнт. У рецепті зазначено дві додаткові характеристики: вартість застосування рецепту понад вартість базової страви та престиж, який додається до престижу базової страви. Шеф-кухар вимірює престиж у власних одиницях, які називаються "одиницями престижу".

Наприклад, список рецептів для приготування піци може виглядати так:

- pizza_tomato pizza_base tomato 1 2
- pizza_classic pizza_tomato cheese 5 5

Тут pizza_base - це елементарна страва, яка не має пов'язаного рецепту, настільки проста, що її вартість незначна (встановлена в $0$), а її престиж також дорівнює $0$. Шеф-кухар може отримати похідну страву pizza_tomato, додавши помідор у базову страву pizza_base за $1$ євро, отримуючи $2$ одиниці престижу. pizza_classic отримується з pizza_tomato шляхом додавання сиру за додаткову плату $5$, а престиж $5$ додається до престижу основної страви; це означає, що загальна вартість pizza_classic становить $6$, а загальний престиж $7$.

Вибір фірмової страви може включати, наприклад, як pizza_tomato, так і pizza_classic. Такий вибір дасть загальний престиж $9$ при загальній вартості $7$. Озброївшись списком рецептів і бюджетом $B$, шеф-кухар хоче представити інспекторам Мішлен фірмовий вибір страв, щоб максимізувати загальний престиж, зберігаючи загальну вартість не більше $B$.

• Жодна страва не може бути обрана двічі у списку фірмових страв.

• Будь-яка страва, яка не вказана як похідна у жодному рецепті, вважається елементарною з вартістю $0$ і престижем $0$.

• Страва може з'являтися у списку рецептів як результативна більше одного разу; якщо є кілька способів отримати страву, обирається той, що дає найменшу загальну вартість при рівних загальних витратах. Якщо загальні витрати однакові, обирається страва з найвищим загальним престижем.

• Рецепти такі, що страву $D$ не можна отримати, додаючи один або кілька інгредієнтів у саму $D$.