308006 - 抄写书稿

有M本书（编号为1，2，…，M），每本书都有一个页数（分别是P_1，P_2，…，P_M）。想将每本都抄写一份。将这M本书分给K个抄写员（1\le K\le M\le500)，每本书只能分配给一个抄写员进行抄写。每个抄写员至少被分配到一本书，而且被分配到的书必须是连续顺序的。抄写工作是同时开始进行的，并且每个抄写员抄写一页书的速度都是一样的。所以，抄写完所有书稿所需时间取决于分配得到最多工作的那个抄写员的抄写时间。

试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小。

第一行两个整数M,K（K\le M\le500）；

第二行M个整数，第i个整数表示第i本书的页数。

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