TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1984
  • Problem
  • P1984【DP】Loongint 的夜晚
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    Loongint和MM在僻静的小镇上居住着,一天晚上,MM对Loongint说:“亲爱的,去把灯关掉。”Loongint十分兴奋,可发现MM亮了整整一排灯……Loongint必须关掉所有的灯……

    开始时他站在某一盏灯的旁边,每盏灯都有一个给定功率的电灯泡,因为Loongint有着自觉的节能意识(表扬),他希望在耗电能总数最少的情况下将所有的灯关掉。Loongint为了积攒精力,所以只能以$1m/s$的速度行走。关灯不需要花费额外的时间,因为当他通过时就能将灯关掉。Loongint需要你在给定路灯设置和灯泡功率的情况下计算以及Loongint的起始位置的情况下关掉所有的灯需耗费的最小能量。

    Input Format

    输入文件的第一行包含一个整数$N(2\leq N\leq 1000)$,表示灯的数量。
    第二行包含一个整数$V(1\leq V\leq N)$,表示Loongint开始关灯的路灯号码。
    接下来的$N$行中,每行包含两个用空格隔开的整数$D$和$W$,用来描述每盏灯的参数。其中$0\leq D\leq 1000,\quad 0\leq W\leq 1000$。$D$表示该灯与这排灯开始处的距离(用米为单位来表示),$W$表示灯泡的功率,即在每秒钟该灯泡所消耗的能量数。
    灯是按顺序输入的。

    Output Format

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

    Sample Input

    4
    3
    2 2
    5 8
    6 1
    8 7

    Sample Output

    56