测试数据来自 system/2469

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　在你面前有一列整数(一共 \(n\) 个)，你要按顺序将其分隔为 \(m\) 部分，各部分内的数字相加，相加所得的 \(m\) 个结果对 10 取模后再相乘得到 \(k\)。游戏的要求 \(k\) 尽量接近但不超过限定的目标整数 \(limit\)。

　　例如：含有 4 个整数序列为：2 -1 3 4，把它们分成 2 部分，\(limit=9\)，则正确的划分方法如下：

　　　　　\(((2-1)\ mod\ 10) * ((3+4)\ mod\ 10) = 1*7 = 7\)

　　注意：整数对 10 取模的结果均为非负值。例如 \(4\ mod\ 10 = 4\)，但是 \(-4\ mod\ 10 = 6\)。

【输入格式】

　　第一行包含三个整数 \(n,m,limit\)，分别表示整数序列长度为 \(n\)，划分成 \(m\) 部分以及限定的目标整数 \(limit\)
　　第二行包含年 \(n\) 个整数，其中第 \(i\) 个的整数表示序列的第 \(i\) 个整数。

【输出格式】

　　如果找不到符合题意的划分，输出"None"。否则在第一行输出接近但不超过limit的最大值，接下来的 \(m\) 行输出对应的划分方案，其中第 \(i+1\) 行表示第 \(i\) 部分的在序列中起点和终点位置（序列的下标从 1 开始），如果有多个划分方法，则输出第一部分长度最小的，如果第一部分最小的仍然有多个划分方法，则输出第二部分长度最小的，……，后面依次类推。

【输入输出样例1】

　Input

4 2 9
2 -1 3 4

　Output

7
1 2
3 4

【输入输出样例2】

　Input

4 2 6
2 -1 3 4

　Output

None

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤n≤30\)，\(1<m≤10\)且\(m≤n\)，\(0≤limit≤2*10^9\)，序列中每个数的绝对值不超过\(2*10^9\)。

【来源】

　　Mr.he