Farmer John为了提高他的奶牛Bessie在比赛时的机动性,Farmer John在Bessie的每条腿上都绑了一根弹簧棍。结果搞得现在一团糟。Bessie现在可以在农场里快速地跳来跳去,但她还没有学会如何放慢速度。
为了帮助训练贝茜更好地控制跳跃,Farmer John为她设置了一个练习课程,沿着穿过农场的直线一维路径。在路径上的不同位置,他放置了N个Bessie应该尝试着陆的目标(1<=N<=1000)。目标i位于位置x(i),如果Bessie落在它上面,则值p(i)点。Bessie从她选择的任何目标的位置开始,只允许在一个方向上移动,从一个目标跳到另一个目标。每一跳必须覆盖至少与前一跳相同的距离,并且必须落在目标上。
Bessie接触到的每个目标(包括她开始的初始目标)都会获得积分。请计算她可以获得的最大分数。