一位渴望获得米其林星级的餐厅主厨想要向评审展示她的一系列招牌菜。为此，她分配了最高预算 $B$ 用于支付累计成本，并希望最大化她向评审展示的菜品的累计声望。

为了衡量菜品的声望，主厨维护了一份食谱列表，其中包含每道菜的成本和配料。对于每份食谱，衍生菜品是通过在基础菜品中添加一种配料而获得的。食谱还提供了两条额外信息：应用该食谱的成本（在基础菜品的成本之上），以及该食谱为基础菜品的声望增加的声望值。主厨用她自己的单位来衡量声望，称为“声望单位”。

例如，一份制作披萨的食谱列表如下： pizza_tomato pizza_base tomato 1 2 pizza_classic pizza_tomato cheese 5 5

在此，pizza_base 是一道基础菜品，即没有关联食谱的菜品，它非常简单，成本可忽略不计（设为 0），声望也为 0。主厨可以通过在基础菜品 pizza_base 中添加配料 tomato 来获得衍生菜品 pizza_tomato，成本为 1 欧元，声望增加 2 个单位。pizza_classic 是通过在 pizza_tomato 中添加 cheese 获得的，增加成本为 5，声望增加 5 个单位；这意味着 pizza_classic 的总成本为 6，总声望为 7。

一份招牌菜选择可以例如同时包含 pizza_tomato 和 pizza_classic。这样的选择将具有 9 的累计总声望和 7 的累计总成本。

有了食谱列表和预算 $B$，主厨希望向米其林评审提供一份招牌菜选择，使得所选菜品的累计总声望最大化，同时保持其累计总成本不超过 $B$。

重要说明

• 在招牌菜选择中，任何菜品不得出现两次。
• 任何未在任何食谱中作为衍生菜品出现的菜品都被视为基础菜品，其成本为 0，声望为 0。
• 一道菜在食谱列表中可以多次作为结果菜品出现；如果获得一道菜的方法不止一种，则始终选择总成本最低的那种；如果总成本相同，则应选择总声望最高的那种。
• 食谱的设定保证没有任何菜品 $D$ 可以通过在 $D$ 本身中添加一种或多种配料而获得。

输入格式

• 第一行包含预算 $B$，为一个整数。
• 第二行包含食谱数量 $N$，为一个整数。
• 接下来的 $N$ 行，每行描述一个食谱，包含由空格分隔的以下元素：衍生菜品名称（字符串）；基础菜品名称（字符串）；添加的配料（字符串）；增加的价格（整数）；增加的声望（整数）。

数据范围

• $0 \le B \le 10\,000$；
• $0 \le N \le 1\,000\,000$；
• 最多有 $10\,000$ 种不同的菜品（基础菜品或衍生菜品）；
• 食谱中的成本和声望在 $1$ 到 $10\,000$ 之间（包含边界）；
• 字符串最多包含 $20$ 个 ASCII 字符（仅限字母、数字和 '_'）。

输出格式

输出应包含两行，每行一个整数。第一行：预算内的最大累计声望。第二行：对应最大累计声望的最小累计成本，该成本必然小于或等于预算。

样例

输入 1

15
6
pizza_tomato pizza_base tomato 1 2
pizza_cheese pizza_base cheese 5 10
pizza_classic pizza_tomato cheese 5 5
pizza_classic pizza_cheese tomato 1 2
pizza_salami pizza_classic salami 7 6
pizza_spicy pizza_tomato chili 3 1

输出 1

25
15