Ингредиенты
Шеф-повар ресторана, претендующий на звезду Мишлен, хочет продемонстрировать инспекторам выбор своих фирменных блюд. Для этого она выделила максимальный бюджет 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 (только буквы, цифры и
_).
Выходные данные
Вывести две строки, каждая из которых содержит одно целое число. В первой строке выведите максимальный накопленный престиж в рамках бюджета. Во второй строке выведите минимальную совокупную стоимость, соответствующую максимальному накопленному престижу, обязательно меньше или равной бюджету.