题目描述

宁智贤得到了一份有趣而高薪的工作。每天早晨她必须关掉她所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。

宁智贤每晚到早晨5点钟都在晚会上，然后她开始关灯。开始时，她站在某一盏路灯的旁边。

每盏灯都有一个给定功率的电灯泡，因为宁智贤有着自觉的节能意识，她希望在耗能总数最少的情况下将所有的灯关掉。

宁智贤因为太累了，所以只能以$1m/s$的速度行走。关灯不需要花费额外的时间，因为当她通过时就能将灯关掉。

编写程序，计算在给定路灯设置，灯泡功率以及宁智贤的起始位置的情况下关掉所有的灯需耗费的最小能量。

输入格式

第一行包含一个整数$N$，$2≤N≤1000$，表示该村庄路灯的数量。

第二行包含一个整数$V$，$1≤V≤N$，表示宁智贤开始关灯的路灯号码。

接下来的$N$行中，每行包含两个用空格隔开的整数$D$和$W$，用来描述每盏灯的参数，其中$0≤D≤1000$，$0≤W≤1000$。

$D$表示该路灯与村庄开始处的距离(用米为单位来表示)，$W$表示灯泡的功率，即在每秒种该灯泡所消耗的能量数。路灯是按顺序给定的。

输出格式

第一行即唯一的一行应包含一个整数，即消耗能量之和的最小值。注意结果小超过$1,000,000,000$。

样例数据

input

4

3

2 2

5 8

6 1

8 7

output

56

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$