题目描述

一条笔直的街道上安装了 $n$ 盏路灯，每盏灯的功率各不相同。工程师小王住在其中一盏灯旁边，他的任务是每天清晨逐一关闭这些路灯。

为了节省电力，小王需要规划关灯顺序，使得从他开始关灯那一刻起，所有灯消耗的总电量最少。小王的行走速度为 $1\,\text{m/s}$，关灯本身不耗时。

每盏灯在被关闭前一直在消耗电能。小王首先关闭自己所在位置的那盏灯，之后可以向左或向右走动去关灯。在行走过程中适当调头有时会更省电。

已知每盏路灯的位置（距街道起点的整数距离，单位 $\text{m}$）和功率（单位 $\text{W}$），请你帮助小王计算出从开始关灯起，所有灯消耗的总电量（单位 $\text{J}$，$1\,\text{J}=1\,\text{W}\times 1\,\text{s}$）。

输入格式

第一行两个正整数 $n$ 和 $c$，分别表示路灯总数和小王所在位置的路灯编号。

接下来 $n$ 行，每行两个整数 $\text{pos}_i$ 和 $w_i$，分别表示第 $i$ 盏路灯的位置和功率。路灯位置按编号递增排列。

输出格式

输出一个整数，即最少的总功耗。

样例

5 3
2 10
3 20
5 20
6 30
8 10

270

提示

数据范围

$1\le n\le 50$，$1\le c\le n$，$1\le w_i\le 100$，$1\le \text{pos}_i\le 100$