만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

폭탄주를 피해라! 파란댕댕이!

시간 제한1초메모리 제한1024 MB

요약
일렬로 놓인 구역의 그룹 인원과 파대엥의 시작 구역이 주어질 때, T초 안에 이동하며 정확히 M명을 모을 수 있는지 판단합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 구간, 완전 탐색
정답자
아직 제출이 없습니다

문제

파댕이는 그동안 학교 공부를 열심히 해서 무사히 댕댕대학교에 진학했다! 파댕이는 MT 여행에서 이 기쁨을 만끽하고 싶었지만, 술을 잘 마시지 못해서 걱정이 이만저만이 아니다.

하지만 이 사실을 알게 되면 댕댕이들이 파댕이만 빼고 친해질 것 같아, 파댕이는 어쩔 수 없이 사실을 숨긴 채 술 게임에 참여했다.

지금 하는 술 게임은 짝 만들기 게임이다. 일렬로 나열된 NN개의 구역이 있고, 각 댕댕이는 원하는 구역에 들어가 같은 구역에 있는 댕댕이끼리 한 무리가 된 채로 시작한다. 그 뒤 다른 무리와 팀을 이뤄 제한 시간 TT초 안에 MM마리로 뭉쳐야 한다. 다른 무리와 팀을 이룰 때 무리 중 일부가 빠질 수 없으며, 팀을 이루지 않은 상황에서도 현재 무리 중 일부가 빠져나갈 수 없다. 제한 시간 내에 MM마리 무리에 속하지 않거나 규칙을 지키지 않은 댕댕이는 벌칙으로 폭탄주를 마셔야 한다.

파댕이를 제외한 나머지 댕댕이들은 그 자리를 지키며 누군가 자신을 데려가기만 기다린다. 폭탄주가 무서운 파댕이는 직접 자신의 무리를 이끌어 MM마리를 만들려 한다. 파댕이가 현재 PP번째 구역에 있으면 1초마다 P−1P-1번째 또는 P+1P+1번째 구역으로 이동할 수 있고, 그 구역에 있는 무리를 데려오거나 지나갈 수 있다. 다른 무리를 데려올 때는 시간이 들지 않으며, 게임을 시작한 지 정확히 TT초가 지났을 때도 다른 무리를 데려올 수 있다.

파댕이가 제한 시간 TT초 안에 MM마리 댕댕이를 무사히 모을 수 있는지 알아보자!

입력

첫 번째 줄에 구역의 수 NN, 사회자가 정한 마릿수 MM, 게임 제한 시간 TT가 공백으로 구분되어 주어진다. (1≤N≤100,1≤M≤100,000,1≤T≤100)(1 \le N \le 100, 1 \le M \le 100,000, 1 \le T \le 100)

두 번째 줄에는 1번째 구역부터 NN번째 구역까지 각 구역에 있는 무리의 댕댕이 수 Q1,Q2,⋯ ,QNQ_{1}, Q_{2}, \cdots, Q_{N}이 공백으로 구분되어 주어진다. (1≤Qi≤1,000)(1 \le Q_{i} \le 1,000)

세 번째 줄에는 시작 전 파댕이가 속한 무리의 위치 PP가 정수로 주어진다. (1≤P≤N)(1 \le P \le N)

출력

파댕이가 폭탄주를 피할 수 있으면 YES, 없으면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    5 8 4
    7 1 2 3 5
    3
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    5 8 3
    7 1 2 3 5
    3
    
    예상 출력
    NO