JOI 2014/2015 예선 4- 간식 배달하기 (Delivery) > 문제은행 : 정보올림피아드&알고리즘




2833 : 간식 배달하기 (Delivery)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
20 회   
시도횟수
53 회   

문제

무더운 날 한울이가 친구들을 위해 간식을 사서 캠프장에 오려고 한다. 한울이의 집에서 캠프장 사이에는 총 N-1개의 은행이 있어서 에어컨이 빵빵하게 틀어져 있다. 모의고사가 M분 뒤에 시작하므로 한울이는 M분 안에 캠프장까지 도착해야 한다. 한울이의 집에서 1번째 은행 사이의 거리는 D1 미터, k-1번째 은행에서 k번째 은행(2 ≤ k ≤ N-1) 사이의 거리는 Dk 미터, N-1번째 은행에서 캠프장 사이의 거리는 DN 미터이다.

 

매 분마다 한울이는 두 가지 선택을 할 수 있다.

1. 1분에 걸쳐 다음 은행/캠프장까지 이동한다. Dk의 값은 한울이가 1분 안에 충분히 갈 수 있을 정도로 작음은 보장되어 있다.

2. 1분 동안 집에서 쉬거나 은행에 들어가서 시원한 바람을 만끽한다.

 

기상청의 날씨 예보에 의하면 매 분마다 불쾌지수를 알 수 있다. 날씨 예보에 의하면 T-1~T분 동안의 불쾌지수는 CT라고 한다.

 

날씨가 매우 덥기 때문에 한울이가 이동하면서 땀을 흘린다. 불쾌지수가 C인 시간대에 D의 거리를 이동하면 한울이는 C × D의 땀을 흘린다. 집이나 은행에서 쉬는 경우 땀을 흘리지 않는다.

 

땀을 많이 흘리고 캠프장에 오면 한울이가 모의고사에 집중을 하기 힘들기 때문에 최대한 땀을 적게 흘리면서 캠프장까지 가려고 한다. 한울이를 도와 땀을 최소 얼마만큼 흘리는지 구하는 프로그램을 작성하여라.

 

※ 예제 1 설명

한울이가 아래와 같은 방법으로 이동하면 땀을 가장 적게 흘린다.

- 0~1분 동안은 집에 있는다.

- 1~2분 동안 은행 1까지 간다. 이때 10 × 30 = 300의 땀을 흘린다.

- 2~3분 동안 은행 2까지 간다. 이때 25 × 15 = 375의 땀을 흘린다.

- 3~4분 동안은 잠시 은행에서 쉰다.

- 4~5분 동안 캠프장까지 간다. 이때 15 × 30 = 450의 땀을 흘린다.


입력형식

첫 번째 줄에는 N과 M이 주어진다. (1 ≤ N ≤ M ≤ 1,000) 두 번째 줄에는 집/은행/캠프장 사이의 거리 Dk가 주어진다. (1 ≤ Dk ≤ 1,000) 세 번째 줄에는 M분 동안의 불쾌지수 C1, …, CM이 주어진다. (1 ≤ Ck ≤ 1,000)

출력형식

한울이가 땀을 흘리는 양의 최솟값을 출력한다.

입력 예

3 5
10 25 15
50 30 15 40 30

출력 예

1125

입력 예

2 6
99 20
490 612 515 131 931 1000

출력 예

31589


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP