Problem C: 古籍图书抄写

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：45 Solved：4

Description

      图书馆中依年代顺序珍藏 n本古藉图书。请了k个志愿者将这些书抄写下来，分给每个志愿者抄写的书是依年代顺序连续的，并且一本书只允许一个人抄写完成。

      可以假设每个志愿者抄写速度是一样的，但每本书的页数是有差别。那么如何分配 k个志愿者的抄写任务使得完成抄写的时间最短。

     例如: 有七本书 三个志愿者来抄写。七本书依年代顺序每本书的页数为 :

      36 53 96 31 12 23 25

      分配给第一个志愿者抄写1，2两本书：第二个志愿者只抄写第3本书：第三个志愿者抄写最后的4本书，完成任务的时间为最短

Input

第一行两个整数 n, k。
第二行 n 个整数，第 i 个整数表示第 i 本书的页数。

Output

共 k 行，每行两个整数，第 i 行表示第 i 个人抄写的书的起始编号和终止编号。 k 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

Sample Input Copy 

7 3
36 53 96 31 12 23 25

Sample Output Copy 

1 2
3 3
4 7

HINT

1≤k≤m≤500，所有古籍书的页数都是正整数且不超过 10^4。