题目描述

加拿大皇家铸币厂设计了一系列新的咖啡桌，其桌腿由不同硬币堆叠而成。每张桌子有四条腿，每条腿使用不同种类的硬币。例如，一条腿可能是由$25$分硬币堆叠而成，另一条腿由$5$分硬币堆叠，第三条腿由$1$加元硬币（$loonie$）堆叠，第四条腿由2加元硬币（$twonie$）堆叠。所有桌腿必须严格等长。

可用的硬币种类繁多，包括外国硬币和纪念币。给定现有的硬币种类及每种硬币的厚度（单位：$0.01$毫米），以及目标桌子的高度（单位：$0.01$毫米），计算最接近目标高度的两种可能桌腿长度：
$1$. 最大可能长度（不超过目标高度）。
$2$. 最小可能长度（不低于目标高度）。

输入格式

$-$每个测试用例以两个整数开头：
$-$ $n$（$4 \leq n \leq 50$）：可用的硬币种类数。
$-$ $t$（$1 \leq t \leq 10$）：需要设计的桌子数量。
$-$接下来的$n$行，每行给出一种硬币的厚度（单位：0.01毫米）。
$-$ 接下来的$t$行，每行给出一个桌子的目标高度（单位：0.01毫米）。
$-$输入以 $0$ $0$ 结束。

输出格式

对于每个目标高度，输出一行两个整数：
$1$. 不超过目标高度的最大可能桌腿长度。
$2$. 不低于目标高度的最小可能桌腿长度。

样例输入 1

4 2
50
100
200
400
1000
2000
0 0

样例输出 1

800 1200
2000 2000

样例解释

$1$. 目标高度1000：
$-$ 最大可能长度800（例如：4×200、4×200、4×200、4×200）。
$-$最小可能长度1200（例如：3×400、3×400、3×400、3×400）。
$2$. 目标高度2000：
$-$ 恰好可用400×5堆叠，因此输出 2000 2000。

关键思路

$1$. 组合计算：从$n$种硬币中选取4种不同硬币，计算它们的最小公倍数（LCM），以确定可能的桌腿长度。
$2$. 查找最接近值：对每个目标高度，在所有可能的LCM组合中，找到不超过和不低于该高度的最接近值。
$3$. 优化处理：由于硬币种类有限（$n \leq 50$），可采用暴力枚举所有4种硬币的组合。

来源

Waterloo local $2004.09.19$