사다리

면접 대비

시간 제한2초메모리 제한64 MB

요약

길이를 줄일 수만 있는 막대 n개로 길이 x인 막대 2개와 길이 y인 막대 k개를 만들 수 있는지 판정한다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬, 배열, 구현
정답자: 아직 제출이 없습니다

문제

길이가 $d_1, d_2, \ldots, d_n$ 인 막대기 $n$ 개가 있다. 사다리를 만들려면 길이 $x$ 인 막대기 2개와 길이 $y$ 인 막대기 $k$ 개, 모두 $k+2$ 개의 막대기가 필요하다. 가지고 있는 막대기를 줄일 수는 있지만, 막대기 하나를 둘로 나눌 수는 없다. 사다리를 만들 수 있을까?

입력

첫 줄에 테스트 케이스의 수 $z$ 가 주어진다. 이어서 각 테스트 케이스의 설명이 주어진다.

각 테스트 케이스는 네 정수 $n$ , $k$ , $x$ , $y$ ( $1 \leq n \leq 10^5$ , $0 \leq k \leq 10^5$ , $1 \leq x, y \leq 10^9$ )와 그 뒤에 오는 $n$ 개의 정수 $d_1$ , $d_2$ , $\ldots$ , $d_n$ ( $1 \leq d_i \leq 10^9$ )로 이루어진다.

출력

각 테스트 케이스마다 사다리를 만들 수 있으면 "YES", 만들 수 없으면 "NO"를 한 줄에 출력한다.

예제1

예제 1

입력

2
8 3 5 2
1 1 1 2 3 4 5 6
8 3 6 2
1 1 1 2 3 4 5 6

예상 출력

YES
NO