[AdditionalFile6990.zip](file://AdditionalFile6990.zip?type=additional_file)

#6990. 「ICPC World Finals 2025」得分值

标签: 传统 | 时间限制: 2000 ms | 内存限制: 2048 MiB |

题目描述

自从你来到你的大学以来，你一直是不懈的倡导者，致力于将一项全新的、结合了武术和纸牌的运动——「搏击桥牌」——引入学校（乃至全世界）。终于，在你（坚持不懈且烦人的）大力倡导下，你从院长那里获得了许可和资金，来为这项运动建造一个宏伟的新场馆！好吧，严格来说，它可能算不上一个「场馆」，更像一个「扫帚间」；也谈不上「宏伟」，不如说它「狭窄」；至于「新」这个字眼，也值得商榷。但未来运动的起点总是朴素的嘛！

不幸的是，你刚刚意识到你需要一个计分显示器来举办比赛。在搏击桥牌中，一支队伍的分数从 $0$ 开始，通过各种可重复的动作，可以增加特定的固定分值。还有一个最大值——如果队伍的分数增加后会超过这个最大值，那么分数将被限制在该最大值。你希望队伍的分数能随时可见，所以你需要准备一些标牌，每个标牌上印有一个数字，用来排列组合显示分数。

不幸的是，院长的「资金」快用完了，而这些标牌很贵。请计算出你需要购买的最少标牌组合，以便能够显示出游戏中可能达成的任何分数。请注意，你不需要购买任何数字 9 的标牌，因为任何数字 6 的标牌倒过来就可以当 9 使用。

输入格式

输入的第一行包含两个整数 $m$ 和 $n$，其中 $m$ $(1 \leq m \leq 10^{18})$ 是最大分值，$n$ $(1 \leq n \leq 10)$ 是不同得分方式的数量。接下来是 $n$ 行，每行包含一个整数 $p$ $(1 \leq p \leq 1000)$，表示游戏中一种动作所能获得的分数。没有两种动作会获得相同的分数。

输出格式

按从 $0$ 到 $8$ 的升序顺序，对于每个数字，输出两个整数：该数字以及你需要购买的带有该数字的标牌数量。如果某个数字所需的标牌数量为 $0$，则省略该行。

样例 1

输入

1000 4
60
100
222
650

输出

0 3
1 1
2 3
3 1
4 3
5 1
6 3
7 2
8 3

样例 2

输入

967 1
1000

输出

0 1
6 2
7 1