本题没有可用的提交语言。

题目描述：

背景

数百年来，世界各地的消防部门一直用水来灭火。遗憾的是，在火灾发生的现场并不总是能找到足够的水源。因此，消防部门配备了大量的水泵和水管，以便将水输送到需要的地方。然而，搭建水泵和水管系统并非易事，因为有诸多限制条件需要考虑。

问题

让我们假设在输水过程中仅使用一种类型的水管，即直径为 $75$ 毫米且长度为 $20$ 米的水管。根据通过水管泵送的水量不同，每米会有一定的压力损失，具体情况如下表所示：

流量（f），单位为升每分钟                      压力损失，单位为毫巴每米

         200                                             1

         400                                             3

         600                                             6

         800                                            10

        1000                                            15

        1200                                            20

压力还会受到地形起伏的影响，更确切地说，每垂直距离 $10$ 米压力就会变化 $1$ 巴（bar），当水管向上爬坡时压力降低，向下坡时压力升高。水泵需要至少 $2$ 巴的输入压力，并且会产生恒定的 $8$ 巴输出压力，但水泵不能用于降低压力。水管无法承受高于 $12$ 巴的压力，并且对于恒定的流量，在所有点都需要至少 $2$ 巴的压力。在水管线路的末端，压力必须至少为 $5$ 巴且至多为 $8$ 巴，以便有效地灭火。在水管线路的起点（位置 $0$）总是有一台水泵。其他水泵可以放置在任意两根水管相互连接的位置，但不能放在线路末端。

编写一个程序，找出所需水泵的最少数量及其位置。如果存在几种水泵数量最少的解决方案，则优先选择那些水泵放置位置更靠近线路起点的方案（搬运这些水泵可一点都不好玩……）。

输入：

第一行包含测试用例的数量。对于每个测试用例，首先会单独有一行给出一个整数 $f$，$f$ 的取值为({200, 400, 600, 800, 1000, 1200})，表示期望的流量（单位：升每分钟）。接下来一行包含两个整数 $n$ 和 $m$，用一个空格隔开，其中 $1 \leq n \leq 20$ 表示要使用的水管数量，$1 \leq m \leq 400$ 表示具有恒定坡度的线段数量。接下来的 $m$ 行描述了这 $m$ 条线段，每行包含两个整数 $l$ 和 $s$，用一个空格隔开，其中 $l > 0$ 表示长度（单位：米），$s$ 表示坡度（以百分比衡量，$s = 10$ 意味着长度为 $100$ 米的水管上升 $10$ 米，$s = -50$ 表示它们下降 $50$ 米；$-100 \leq s \leq 100$。可以保证给出的 $m$ 个长度之和等于 $n$ 乘以 $20$ 米。

输出：

对于每个测试用例的输出，首先是一行包含 “Scenario #i:” 的内容，其中i是测试用例的编号，从 $1$ 开始。下一行包含最优解决方案中水泵的数量（如果存在这样的方案），接着是一个冒号 $:$ 和一个空格，然后是水泵的位置，这些位置之间用逗号 $,$ 隔开，且没有空格。如果不存在满足给定条件的水泵放置方案，则打印一行包含 "no solution" 的内容来代替。每个测试用例的输出最后再额外添加一个空行。

输入数据1

2
600
7 3
70 50
30 -25
40 25
1000
8 4
20 0
80 -100
20 10
40 30

输出数据1

Scenario #1:
2: 0,2

Scenario #2:
no solution

来源：

2002 年德国达姆施塔特工业大学编程竞赛