#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 50010;const int p = 10007; int n, m, sm, mx;int val[maxn], sum[maxn];int f[2][maxn];bool check(int x){ int res = 0, tmp = 0; for(int i = 1; i <= n; i ++){ if(tmp + val[i] <= x) tmp += val[i]; else tmp = val[i], res ++; } return res <= m;}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) scanf("%d", &val[i]), sm += val[i], mx = max(mx, val[i]); for(int i = 1; i <= n; i ++) sum[i] = sum[i-1] + val[i]; int l = mx, r = sm, ans = 0; while(l <= r){ int mid = (l+r) >> 1; if(check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } int now = 0, res = 0; for(int i = 1; sum[i] <= ans; i ++) f[now][i] = 1; for(int i = 1; i <= m; i ++){ int ll = 0, rr = 0, x = 0; now ^= 1; for(int j = 1; j <= n; j ++){ while(rr < j-1) x = ((x+f[now^1][++rr])%p+p)%p; while(sum[j]-sum[ll] > ans) x = ((x-f[now^1][ll++])%p+p)%p; f[now][j] = x; } res = (res+f[now][n])%p; } PRintf("%d %d", ans, res); return 0;}
