OI总部最近得到可靠消息，近日来怪盗基德会再次来OI总部盗窃机密文件（因为是机密，所以不能透露=  =||）。所以OIER得在怪盗基德来临之前就把文件备份。不过，正好今天OI总部停电了（说停就停，什么素质！），所以就得人工抄写了#-#。现在，OI总部内一共有M份资料和K个OIER（S），需要将每一份资料都备份一份，M份资料的页数不一定相同（有不同的，也有相同的）。现在，你作为其中的一名OIER（当然你是不干活的，因为你牛！），把资料分配给OIER备份，由于人太多了（大多是无名小卒），所以每一名OIER所分配到的资料都必须是连续顺序的，并且每一名OIER的备份速度是相同的。你的任务就是让备份的时间最短，列出最短的方案，数据可能存在多个解，所以，当存在多个解时，让前面的人少备份（先来先休息^-^）。

第一行有两个整数：M，K。表示书本的数目和OIER的人数。
第二行：由M个分隔的整数构成，分别表示M本书的页数。
(第I份资料的编号为I)。
对于50%的数据，(1<=k<=m<=500)；
对于全部的数据，(1<=k<=m<=1000)的离散随机数据。

共K行： 每一行都由两个整数。：
第I行表示第I个OIER备份的资料编号的起止。

8 3
1 2 3 4 5 6 7 8

1 3
4 6
7 8