수직선 위에 N개의 구멍이 뚫려있다. 우리가 할 일은 나무판자를 사서 구멍 N개를 모두 덮는 것이다. 나무판자는 너비 별로 가격이 다르다. 만약 x_i~x_j까지 덮는 다면 판자의 너비는 x_j-x_i+1이 되며 판자의 가격은C_xj-xi+1이 된다. 판자의 너비가 좁다고 해서 넓은 것 보다 가격이 저렴할 필요는 없다. 나무판자 여러 개를 사용할 때, 구멍을 모두 덮는 최소 가격을 알아내자.

첫 줄에 구멍의 수 N과 수직선의 길이 M이 주어진다. 둘째 줄에 자연수인 구멍의 x 좌표가 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ 100,000, 1 ≤ x_i ≤ M, x_i 는 서로 다르다) 다음 M개의 줄에 각 너비 별로 판자의 가격이 주어진다. i+2 번째 줄에 들어오는 값은 C_i 이며, 너비가 i인 나무판자의 가격이다. (1 ≤ C_i ≤ 1,000,000)

첫 줄에 구멍을 모두 덮는 최소 비용을 출력한다.

KOI4U 2012 2월 모의고사