小z是一条小虫，它误入了一个零食桶，小Z现在在零食桶中间某一个零食边上，由于零食会随着时间流失变得不好吃，

现在给出，每种零食的位置和营养流失率，小z尽快的去吃掉零食，但是小z不知道怎样去规划吃零食才可以尽可能少的流失掉营养。

它首先吃掉自己所处位置的零食，然后可以向左也可以向右去吃零食。开始他以为先算一下左边零食的营养总丢失率再算一下右边零食的营养总丢失率，然后选择先吃掉零食的营养总丢失率多的一边，再回过头来吃另外一边，而事实并非如此，因为在吃的过程中适当地调头有可能会丢失的少一些。

现在已知小Z蠕动的速度为 1单位/s，每种零食的位置（是一个整数，即距路线起点的距离），每种营养丢失率，小z吃的很快，所用的时间很短而可以忽略不计。

请你为小z编一程序来安排吃零食的顺序，使从小z开始吃零食算起所有零食丢失掉的营养最少。

第一行是两个数字 n（表示零食的总数）和 c（小z所处第几个零食的位置）；

接下来 n 行，每行两个数据，表示第 1 种零食到第 n 总零食的位置和营养流失率。数据保证位置单调递增。

一个数据，即最少丢失掉的营养

样例解释

吃零食顺序为 `3 4 2 1 5`，丢失270营养是最少的。

数据范围

50%的数据： 1\le n\le50，1\le c\le n。

100%的数据： 1\le n\le 3000，1\le c\le n。数据保证总丢失率是在long long范围