산이 높고 험하기로 유명한 에베레스트에는 N+1개의 베이스캠프가 있고, 산 아래부터 베이스캠프 0번, 베이스캠프 1번, ..., 베이스캠프 N번(에베레스트 정상)으로 정해진다. 베이스캠프 i-1번와 베이스캠프 i번 (1≦i≦N) 사이의 거리는 Di이다.

등반가인 준용이는 베이스캠프 0번에서 출발하여 캠프를 차례로 경유하여 베이스캠프 N번(에베레스트 정산)까지 등반하게 결심하였다. 베이스캠프 0번에서 베이스캠프 N(에베레스트 정산)까지 주어진 M시간 이내에 이동해야한다. 준용이는 베이스캠프에 머무는 매 시간마다 다음 두 가지 중 하나를 선택한다.

이동할 때마다 피로도가 쌓여 간다. 에베레스트에서는 매 시간마다 날씨변화가 나쁜 정도에 따라 이동에 어려움이 측정된다.(날씨가 나쁘면 수치는 커진다.)

준용이는 발달된 일기예보를 통해서 j시간(1≦j≦M)일 때 날씨로 인한 이동의 어려움이 Cj가 되는 것을 알고 있다. 만약 j시간일 때, 베이스캠프 i-1번에서 베이스캠프 i번으로 이동하는 경우, 피로도가 Di × Cj 만큼 쌓이게 된다. 하지만 이동하지 않고 기다리는 시간에는 피로도가 쌓이지 않는다.

준용이가 매 시간에 이동할지, 대기할지 잘 선택하여 가능한 피로도를 최소화하여 산 정상에 등극하고 싶다. 준용이가 M 시간 이내에 베이스캠프 N(에베레스트 정상)으로 이동할 때의 피로도 총합의 최소값을 구하라.