Under construction

Still being built. Things may change

Avoid the bomb shot! Blue Padaengi!

Time limit1sMemory limit1024 MB

Summary
Given dog groups in a row of zones and Padaengi's start zone, decide whether Padaengi can walk within T seconds and collect exactly M dogs.
Level

Medium5 of 10

Topics
Dynamic programming, Intervals, Brute force
Solved
No attempts yet

Problem

Padaengi studied hard in school and entered Dangdaeng University. Padaengi wanted to enjoy the joy of this success on an MT trip, but Padaengi does not drink well and is very worried.

If the others found out, they would become close without Padaengi, so Padaengi hid the fact and joined the drinking game.

The drinking game is a pairing game. NN zones are lined up in a row. Each dog enters the zone of its choice, and dogs in the same zone start as one group. Then each group forms a team with another group, and they must gather into groups of MM dogs within TT seconds. When a group joins another group, no member may leave it, and even before teaming up, a group cannot let any of its members leave. A dog that is not in a group of MM dogs within the time limit, or that breaks the rules, must drink the bomb shot as a penalty.

The other dogs stay where they are and wait for someone to take them. Padaengi fears the bomb shot and plans to lead a group of MM dogs personally. If Padaengi is in zone PP, Padaengi can move to zone P−1P-1 or zone P+1P+1 in 1 second, and can take or pass through the group in that zone. Taking another group costs no time, and Padaengi can still take another group at the exact moment TT seconds have passed since the game started.

Can Padaengi gather MM dogs within the time limit TT seconds and avoid the bomb shot?

Input

The first line contains three integers: the number of zones NN, the number MM set by the host, and the time limit TT in seconds, separated by spaces. (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)

The second line contains integers Q1,Q2,⋯ ,QNQ_{1}, Q_{2}, \cdots, Q_{N}, the number of dogs in each group in zones 1 through NN, separated by spaces. (1≤Qi≤1,000)(1 \le Q_{i} \le 1,000)

The third line contains the integer PP, the zone where Padaengi's group is located at the start. (1≤P≤N)(1 \le P \le N)

Output

Print YES if Padaengi can avoid the bomb shot, and NO otherwise.

Examples2

  1. Example 1

    Input
    5 8 4
    7 1 2 3 5
    3
    
    Expected output
    YES
    
  2. Example 2

    Input
    5 8 3
    7 1 2 3 5
    3
    
    Expected output
    NO