재료

미슐랭 별을 노리는 어느 식당의 주방장이 심사원에게 내놓을 대표 요리를 고르려고 한다. 고른 요리의 총비용에 쓸 수 있는 예산은 B이고, 주방장은 그 안에서 내놓는 요리의 총명성을 최대로 만들고 싶어 한다.

주방장은 요리법 목록을 비용, 재료와 함께 관리한다. 요리법 하나는 바탕 요리에 재료 하나를 더해 파생 요리를 만든다. 요리법에는 바탕 요리의 비용에 더해지는 비용과 바탕 요리의 명성에 더해지는 명성이 함께 적혀 있다. 명성은 주방장이 직접 정한 단위인 명성 단위로 센다.

피자 요리법 목록은 다음과 같이 생겼다.

pizza_tomato pizza_base tomato 1 2
pizza_classic pizza_tomato cheese 5 5

pizza_base는 기본 요리다. 이 요리를 만드는 요리법이 없으므로 비용도 0이고 명성도 0이다. pizza_base에 tomato를 더하면 비용 1유로와 명성 2를 얹어 pizza_tomato가 된다. pizza_tomato에 cheese를 더하면 비용 5와 명성 5가 더 붙어 pizza_classic이 되므로, pizza_classic의 총비용은 6이고 총명성은 7이다.

대표 요리 선택에는 pizza_tomato와 pizza_classic을 함께 넣어도 된다. 이 선택의 총명성은 9, 총비용은 7이다.

요리법 목록과 예산 B가 주어진다. 총비용을 B 이하로 유지하면서 고른 요리의 총명성을 최대로 하라.

규칙

• 같은 요리를 선택에 두 번 넣을 수 없다.
• 어떤 요리법에서도 파생 요리로 등장하지 않는 요리는 기본 요리이며, 비용과 명성이 모두 0이다.
• 한 요리가 여러 요리법의 파생 요리로 등장하기도 한다. 만드는 방법이 둘 이상이면 언제나 총비용이 가장 작은 방법을 따르고, 총비용이 같으면 총명성이 가장 큰 방법을 따른다.
• 요리 D에 재료를 하나 이상 더해 D 자신을 다시 만드는 일은 없도록 요리법이 주어진다.

• 첫째 줄에 예산 B가 정수로 주어진다.
• 둘째 줄에 요리법의 수 N이 정수로 주어진다.
• 다음 N개 줄에 요리법이 한 줄에 하나씩, 공백 하나로 구분한 다섯 값으로 주어진다. 파생 요리의 이름(문자열), 바탕 요리의 이름(문자열), 더하는 재료(문자열), 더해지는 비용(정수), 더해지는 명성(정수) 순이다.

제한

• $0 \le B \le 10000$
• $0 \le N \le 1000000$
• 서로 다른 요리는 기본 요리와 파생 요리를 합쳐 최대 10000가지다.
• 요리법에 적힌 비용과 명성은 모두 1 이상 10000 이하다.
• 모든 문자열은 ASCII 문자 20자 이하이며 영문자, 숫자, 밑줄만 쓴다.

두 줄에 정수를 하나씩 출력한다. 첫째 줄에는 예산 안에서 얻을 수 있는 최대 총명성을 출력한다. 둘째 줄에는 그 최대 총명성을 내는 총비용 가운데 가장 작은 값을 출력한다. 이 값은 B 이하다.