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

• существует не более 10 000 различных блюд (элементарных или производных);
• стоимость и престиж в рецептах варьируется от 1 до 10 000 (включительно);
• строки содержат не более 20 символов ASCII (только буквы, цифры и _).

Выходные данные

Вывести две строки, каждая из которых содержит одно целое число. В первой строке выведите максимальный накопленный престиж в рамках бюджета. Во второй строке выведите минимальную совокупную стоимость, соответствующую максимальному накопленному престижу, обязательно меньше или равной бюджету.