Problem 4878. -- Poj1821 Fence

4878: Poj1821 Fence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 17  Solved: 1
[Submit][Status][Web Board]

Description

一个有N(1<=N<=16000)个木板的栅栏,由K(1<=k<=100)个工人粉刷. 
一开始每个工人坐在编号为Si的木板前. 
每个工人只能粉刷一串连续的,不大于Li,并且包含Si的木板. 
第i个工人每粉刷一块木板的工钱为Pi$ (1<=Pi<=10000) 
求得所有工人最多能得到的工钱

Input

Output


Sample Input

84
322
323
335
117

Sample Output

17

HINT

Source

[Submit][Status]