TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1175
  • Problem
  • P1175关灯
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    多瑞卡得到了一份有趣而高薪的工作。每天早晨他必须关掉他所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。
    多瑞卡每晚到早晨5点钟都在晚会上,然后他开始关灯。开始时,他站在某一盏路灯的旁边。
    每盏灯都有一个给定功率的电灯泡,因为多端卡有着自觉的节能意识,他希望在耗能总数最少的情况下将所有的灯关掉。
    多端卡因为太累了,所以只能以1m/s的速度行走。关灯不需要花费额外的时间,因为当他通过时就能将灯关掉。
    编写程序,计算在给定路灯设置,灯泡功率以及多端卡的起始位置的情况下关掉所有的灯需耗费的最小能量。

    Input Format

    第一行包含一个整数N,2≤N≤1000,表示该村庄路灯的数量。
    第二行包含一个整数V,1≤V≤N,表示多瑞卡开始关灯的路灯号码。
    接下来的N行中,第i行表示第i盏灯,每行包含两个用空格隔开的整数D和W,用来描述每盏灯的参数,其中0≤D≤1000,0≤W≤1000。D表示该路灯与村庄开始处的距离(用米为单位来表示),W表示灯泡的功率,即在每秒种该灯泡所消耗的能量数。路灯是按顺序给定的。

    Output Format

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

    Sample Input

    4
    3
    2 2
    5 8
    6 1
    8 7

    Sample Output

    56

    Hint

    编号越大的灯离村庄越远
    样例说明:
    3-->2-->4-->1