TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1984
  • 题目
  • P1984【DP】Loongint 的夜晚
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Loongint 和 MM 在僻静的小镇上居住着,一天晚上,MM 对 Loongint 说:“亲爱的,去把灯关掉。”Loongint 十分兴奋,可发现 MM 亮了整整一排灯…Loongint 必须关掉所有的灯…开始时他站在某一盏灯的旁边,每盏灯都有一个给定功率的电灯泡,因为 Loongint有着自觉的节能意识(表扬),他希望在耗电能总数最少的情况下将所有的灯关掉。Loongint为了积攒精力,所以只能以 1m/s 的速度行走。关灯不需要花费额外的时间,因为当他通过时就能将灯关掉。Loongint 需要你在给定路灯设置和灯泡功率的情况下计算以及Loongint 的起始位置的情况下关掉所有的灯需耗费的最小能量。

    输入格式

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

    输出格式

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

    样例输入

    4
    3
    2 2
    5 8
    6 1
    8 7

    样例输出

    56