입대

• 약간의 변형을 거치면 흔한 형태의 DP 문제로 바꿀수 있다.
• M점 이상을 모을수 있는 최소 헌혈횟수를 구하기 위해서, 헌혈 횟수가 0번일때의 최대 점수, 1번일때의 최대 점수, …, K번일때의 최대 점수를 각각 구한다음에, 최초로 M점이 넘어가는 횟수를 구한다고 생각하자. 특정 선택지의 사용 횟수를 기록하며 최적값을 구하는 형태의 DP는 흔한 유형이다. 선택지의 사용횟수의 제한이 없을때의 최적값을 구하는 문제에서, 상태공간이 K배 늘어나니까, 시간복잡도도 K배가 늘어나는 식으로 처리된다.
• 그러면, 선택지 횟수 제한은 그렇게 처리한다치고, 선택지의 횟수 제한이 없다고 생각했을때, N일까지 얻을수 있는 최대 점수를 구하는 문제는 어떻게 모델링하면 될까?
• 문제를 일반화시키면, 매번 고를수 있는 선택지들이 있고, 특정 선택지를 고르면 앞으로 d번동안 선택지가 제한되는 형태이고, 흔한 1차원 DP 유형이다. 이런 문제에서 종종 실수하는 비효율적인 모델링은, i일까지 진행했고 앞으로 j일동안은 선택지가 제한되는 상태에서의 최대값을 dp[i][j]로 모델링하는 것이다. 계산이 불가능한것은 아니지만, 이러면 시간복잡도가 O(nD)가 되어서 비효율적이 된다.
• 이 경우를 효율적으로 모델링하는 방법은, 이 문제를 기준으로 설명하면, '헌혈하고 D일동안 쉬는' D일동안의 스케쥴을 하나의 액션으로 취급하는 것이다. 그러면 dp[i] 는 i일째에서 모든 선택지를 사용가능한 상태에서의 최댓값이 된다. dp[i] = max(dp[i-1]+{봉사활동 이득} + dp[i-D]+{헌혈 이득}) 으로 점화식을 세울수 있다. 헷갈리지 않도록 다시한번 설명하면, 여기서 dp[i-D]+{헌혈 이득}로 처리하는 경우는, 오늘 헌혈을 하는 상황이 아니라 D일전에 헌혈을 했을때의 상황을 처리해준 것이다.
• 이렇게 처리할때 주의할 점은 마지막 날 직전 d일 안에 헌혈을 하는 것은 처리되지 않는다는 점이다. 이것을 처리하는 방법은 몇가지 있다
  • 하나는 날짜 범위를 n+d일까지로 늘려서 계산한 뒤에 n+d일째의 값, dp[n+d]을 취하는 것이다. 이렇게 하기 위해서는 i일 이후의 봉사활동의 이득은 전부 0점으로 세팅하면 된다.
  • 다른 방법은 dp테이블을 채워놓고, 최종 답을 max_{k⇐d}(dp[n-k] +{봉사활동 이득}) 이런식으로 따로 구해주는 방법도 있다.
  • 또 다른 방법은, dp테이블을 마지막날부터 첫날쪽으로 역순으로 채우는 것이다. 'D일전에 봉사활동하고 D일동안 휴식하는' 선택 대신에, 'D일동안 휴식하고 오늘 봉사활동하는' 선택으로 바뀌게 되어서, 위에서 말한 문제가 보다 깔끔하게 해결된다. 실제로도 이 방식으로 구현했다.
• 그러면 이제 헌혈횟수의 제한이 없는 경우는 O(n)에 구할수 있다.
• 헌혈횟수에 따라서 dp값을 따로따로 저장하게 되면, dp[i][j] = max(dp[i-1][j]+{봉사활동 이득} + dp[i-D][j-1]+{헌혈 이득}) 형태로 점화식을 세우면 된다. 시간복잡도는 O(nk)가 된다.
• 이 점화식을 2중 루프로 계산할때는, 원래 1차원 DP식을 확장하는 느낌으로는 바깥루프에 i를, 안쪽 루프에 j를 놓는게 직관적일수 있는데, 이것을 바꿔서 바깥루프에서 j를 처리하는것이 좀더 유리하다. i쪽은 이전 D칸까지를 저장하고 있어야 하지만, j쪽은 이전 1칸만 저장하면 충분하기 떄문에, 이렇게 두면 토글링을 사용할수 있다.

"""Solution code for "BOJ 31413. 입대".

- Problem link: https://www.acmicpc.net/problem/31413
- Solution link: http://www.teferi.net/ps/problems/boj/31413

Tags: [dp]
"""


def main():
    N, M = [int(x) for x in input().split()]
    s = [int(x) for x in input().split()]
    A, D = [int(x) for x in input().split()]

    v = 0
    dp_cur = [v := v + s_i for s_i in reversed(s)][::-1]
    if dp_cur[0] >= M:
        print('0')
        return

    for j in range(1, N + 1):
        dp_prev, dp_cur = dp_cur, [None] * N
        dp_cur[N - 1] = max(s[N - 1], A)
        for i in reversed(range(N - 1)):
            if i + D < N:
                dp_cur[i] = max(dp_cur[i + 1] + s[i], dp_prev[i + D] + A)
            else:
                dp_cur[i] = max(dp_cur[i + 1] + s[i], A)
        if dp_cur[0] >= M:
            print(j)
            break
    else:
        print('-1')


if __name__ == '__main__':
    main()