UOJ Logo

NOI.AC

1S 512MB

#1279. Gakkipan的手环

Statistics

题目描述

Gakkipan有一个手环,手环由n个珠子构成,每个珠子上有一个值,Gakkipan想把这个手环拆成m段,每一段的价值为所有珠子值的和对10取模,如果为负数,再加上10。最后的需要你求出m段价值乘积的最小值和最大值。

例如,下面这个手环($n=4,m=2$):

最小值为$((2-1) \mod 10) \times ((4+3) \mod 10)=1×7=7$ 最大值为$((2+4+3) \mod 10) \times (-1 \mod 10)=9×9=81$。

输入

输入第一行有两个整数,$n(1≤n≤50)$和$m(1≤m≤9)$。以下$n$行每行有个整数,其绝对值不大于$10^4$,按顺序给出手环上每个珠子的值,首尾相连。

输出

输出有两行,各包含一个非负整数。第一行是最小值,第二行是最大值。

样例输入

4 2
4
3
-1
2

样例输出

7
81