늑대 구덩이

바이토티아의 왕 바이에타사르 3세는 적의 성을 공격할 계획을 세우고 있다. 성은 세 면이 건널 수 없는 해자로 둘러싸여 있어, 바이에타사르는 네 번째 면을 공성하는 것 외에 다른 선택지가 없다. 그러나 그 면도 완전히 무방비는 아니다. 왕의 정찰병들은 이 벽을 따라 깊은 늑대 구덩이가 있다고 보고했다. 바이에타사르는 벽의 연속한 구간 중 가능한 한 긴 구간을 공격하고 싶어 한다. 그러기 위해서는 늑대 구덩이 일부를 무력화해야 한다. 현명한 왕은 그중 일부는 모래로 메우고, 일부는 대판자로 덮기로 했다.

벽을 따라 늑대 구덩이가 n개 있다. 왕의 군대에는 모래주머니가 p개 있다. i번째 늑대 구덩이를 메우려면 모래주머니 wi개가 필요하다. 또한 대판자는 연속한 늑대 구덩이를 최대 d개까지 덮을 수 있다.

군대가 자원(모래주머니와 대판자)을 최적으로 사용할 때 공격할 수 있는 벽의 가장 긴 구간을 찾아 바이에타사르를 도와라. 즉, 무력화할 수 있는 연속한 늑대 구덩이의 최대 개수를 구하라.

첫째 줄에 늑대 구덩이의 수, 모래주머니의 수, 대판자의 길이를 나타내는 정수 n, p, d가 공백 하나를 사이에 두고 주어진다. (1 ≤ d ≤ n ≤ 2 000 000, 0 ≤ p ≤ 10^16)

다음 줄에는 늑대 구덩이를 나타내는 n개의 정수 w1, w2, ..., wn이 공백 하나를 사이에 두고 주어진다. (1 ≤ wi ≤ 10^9) wi는 i번째 늑대 구덩이를 메우는 데 필요한 모래주머니의 수이다. 전체 점수의 30%에 해당하는 테스트에서는 n ≤ 3000이라는 조건이 추가로 성립한다.

첫째 줄에 왕의 군대가 공격할 수 있는 벽의 가장 긴 연속 구간의 길이를 나타내는 정수 하나를 출력한다.

2, 3, 6번 늑대 구덩이는 모래로 메울 수 있고(가진 주머니 7개 중 6개를 사용), 4, 5번은 대판자로 덮을 수 있다. 이렇게 하면 연속한 늑대 구덩이 5개(2번부터 6번)를 무력화할 수 있다.