题目描述

NOIP 2003

楚继光根据张琪曼的研究结果设计了一款《模拟人生一卡耐鸡人生指南》的电脑游 戏.此款游戏着重于经营自己的人生.玩家一开始便要设定自己的人生目标,包括了快乐、财 富、降、名誉、道德和智慧六种指数,玩家必须在$\red{70}$岁之前想办法达到自己设定的目标。 初始时玩家各项指标的设定遵守这样的游戏规则:在玩家面前有一圈整数(一共$\red{N}$个),玩 家要按顺序将其分为$\red{M}$个部分,各部分内的数字相加，相加所得的$\red{M}$个结果对$\red{10}$取模后 再相乘,最终得到一个数$\red{K,}$而如何划分使所得的$\red{K}$最大或者最小将决定玩家在游戏中的 幸运值。现在请你帮助玩家获得最大的幸运值。

例如,对于图中的数字$\red{(N=4，}$$\red{M=2):}$

当要求最小值时,$\red{[(2- 1)\%10]\times [(4+3)\%10]=1\times 7-7,}$要求最 大值时,为$\red{[(2+4+ 3)\%10]\times (- 1\%10)=9\times 9=81}$。特别值得注意的 是,无论是负数还是正数,对$\red{10}$取模的结果均为非负值。

输入格式

输入文件第一行有两个整数$\red{N(1≤}$$\red{N≤}$$\red{50)}$和$\red{M(1≤}$$\red{M≤}$$\red{9)}$。以下$\red{N}$行每行有$\red{1}$个整 数，其绝对值不大于$\red{10 000,}$按顺序给出圈中的数字,首尾相接。

输出格式

输出最小值和最大值。

样例

输入样例

4 2
4
3
-1
2

输出样例

7
81