dovelet/problems/race1

f(n) = (n번 째 station까지 지나갈 때의 시간의 최솟값. n번 째 station은 반드시 방문)
g(n) = (n번 째 station을 방문 할 때 소요되는 시간)
문제에서는 n개의 station 정보(f(0), ... f(n - 1))만 주지만, 마지막 station의 방문 소요 시간((f(n))을 0으로 기록해두자.

n번 째 station에서 다른 station을 방문하지 않고 가장 뒤로 멀리 갈 수 있는 station을 m이라고 하면 f(n) = min(f(m), f(m + 1), ... f(n - 1)) + g(n) 이 성립한다.

계산을 마치면 f(n)이 답.

시간 복잡도는 O(n^2). binary indexed tree를 사용한다면 O(nlogn)까지 기대.

주의사항으로는, 마지막 10번 input data는 자기 멋대로 \n으로 중간에 input을 잘라버린다. 아래 코드처럼 line 단위로 입력을 받는 경우 터짐. 도블릿을 깝시다.

10번 input data의 경우 dovelet에서 임의로 input에 대해 line wrap을 해버리기 때문에 입력을 제대로 받지 못해서 틀려버린다. 주의.

case_limit = int(input())
case_length = int(input())
case_distance = [int(x) for x in input().split()] + [0]
case_time = [int(x) for x in input().split()] + [0]

list_time = [0]

for i in range(0, case_length + 1):
    distance = case_distance[i]
    left_index = i

    while left_index > 0 and distance + case_distance[left_index - 1] <= case_limit:
        left_index -= 1
        distance += case_distance[left_index]

    list_time.append(min(list_time[left_index:i + 1]) + case_time[i])

print(list_time[-1])