Інгредієнти
Шеф-кухар ресторану, який прагне отримати зірку Мішлен, хоче вразити інспекторів, представивши їм вибір своїх фірмових страв. Для цього вона виділила максимальний бюджет 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.
Вхідні дані
Перший рядок містить ціле число - бюджет B (0 ≤ B ≤ 10 000). Другий рядок містить кількість рецептів n (0 ≤ n ≤ 10^6). Кожен з наступних n рядків описує рецепт у вигляді наступних елементів, розділених пробілами: назва похідної страви (рядок); назва базової страви (рядок); доданий інгредієнт (рядок); додана ціна (ціле число); доданий престиж (ціле число).
Існує не більше 10 000 різних страв (елементарних або похідних);
Вартість і престиж у рецептах варіюються від 1 до 10 000 (включно);
Рядки містять не більше 20 символів ASCII (тільки літери, цифри та
_).
Вихідні дані
Виведіть два рядки, кожен з яких містить одне ціле число. У першому рядку виведіть максимальний накопичений престиж у межах бюджету. У другому рядку виведіть мінімальну сукупну вартість, що відповідає максимальному накопиченому престижу, обов'язково меншій або рівній бюджету.