关路灯
测试数据来自 system/1182
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【问题描述】
某一村庄在一条路线上安装了 \(N\) 盏灯(依次标号 \(1..N\)),每盏灯都有各自的位置和功率(即每秒消耗的电量)。
老张就住在路灯 \(P\) 旁,他每天早上的第一件事就关掉这些路灯:首先会关掉路灯 \(P\),然后可以向左也可以向右去关其他灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率,然后选择先关掉功率大的一边,再回过头来关掉另一边的路灯,而事实并非如此,因为在关的过程中适当地调头有可能会更省一些。
已知老张走的速度为 \(1m/s\),老张关灯所用的时间可以忽略不计。请你编一程序来安排老张的关灯顺序,使从老张开始关灯时刻算起所有灯的耗电量之和最少。
【输入格式】
第一行包含一个整数 \(N\) 表示该村庄路灯的数量。
第二行包含一个整数 \(P(1≤P≤N)\),表示老张开始在路灯 \(P\) 旁。
接下来有 \(N\) 行,每行包含两个整数:\(X\) 和 \(W\)。表示路灯路线开始处的距离为 \(X\) 米,功率为 \(W\) 瓦。路灯是按顺序给定的。
【输出格式】
输出一个整数,即耗电量的最小值。
【输入输出样例】
Input
5
3
2 10
3 20
5 20
6 30
8 10
Output
270
【数据限制】
对于 \(20\%\) 数据有:\(N≤25\);
对于 \(50\%\) 数据有:\(N≤50\);
对于 \(100\%\) 数据有:\(N≤1000,0≤X≤10000,0≤W≤1,000,000,000\)。
【来源】
Mr.he