P15222 [SWERC 2017] Ingredients

一位渴望获得米其林星级的餐厅厨师希望向评审展示她的招牌菜肴。为此，她为累计成本设定了最大预算 $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 的总成本为 $1 + 5 = 6$ ，总声望为 $2 + 5 = 7$ 。 招牌菜肴选择可以同时包含 pizza_tomato 和 pizza_classic 。这样的选择累计总声望为 $2 + 7 = 9$ ，累计总成本为 $1 + 6 = 7$ 。 凭借食谱列表和预算 $B$ ，厨师希望为米其林评审提供一份招牌菜肴选择，使得菜肴的累计总声望最大化，同时保持累计总成本不超过 $B$ 。 #### 重要提示 - 同一道菜肴不能在招牌菜肴选择中出现两次。 - 任何未在任何食谱中作为衍生菜肴出现的菜肴均被视为初级菜肴，其成本为 0 ，声望为 0 。 - 一道菜肴可以在食谱列表中多次作为结果菜肴出现；如果存在多种方式获得该菜肴，则总是选择总成本最小的方式；如果总成本相同，则应选择总声望最高的方式。 - 食谱保证没有菜肴 $D$ 能够通过向 $D$ 自身添加一种或多种原料而获得。

- 第一行包含预算 $B$ ，一个整数。 - 第二行包含食谱数量 $N$ ，一个整数。 - 接下来的 $N$ 行每行描述一道食谱，包含以下由单个空格分隔的元素：衍生菜肴名称（字符串）、基础菜肴名称（字符串）、添加的原料（字符串）、额外价格（整数）、额外声望（整数）。

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

### 数据范围 - $0 \leq B \leq 10000$ ； - $0 \leq N \leq 1\,000\,000$ ； - 最多有 10000 道不同的菜肴（基础或衍生）； - 食谱中的成本和声望介于 1 到 10000 之间（含）； - 字符串最多包含 20 个 ASCII 字符（仅字母、数字和下划线 ‘_’）。 翻译由 DeepSeek 完成