Cosmin ran into another existential problem. He has N girlfriends and M pairs of shoes. He knows the height hi of each girlfriend (1 ≤ i ≤ N), and the increase in height sj that each pair of shoes provides when worn (1 ≤ j ≤ M).

Because of his shallow personality, he does not want to be seen with any girlfriend who is too short or too tall for him. In order to avoid this problem, he chose an acceptable height interval [hMin, hMax]. For each girlfriend, he can choose to gift her one pair of shoes to increase her height, or do nothing. Each girlfriend can wear at most one pair of shoes, and each pair of shoes can be given to at most one girl.

Your task is to find out whether or not Cosmin can get all of his girlfriends' heights in the acceptable interval.


The first line of input contains four integers: N, M, hMin and hMax.
The second line of input contains N space-separated values: h1, …, hN.
The third line of input contains M space-separated values: s1, …, sM.


A single word: Yes or No, whether or not Cosmin can achieve his goal.


  • 1 ≤ N, M ≤ 1000
  • 1 ≤ hi ≤ 1000
  • 1 ≤ sj ≤ 1000
  • 1 ≤ hMin ≤ hMax ≤ 1000


3 2 165 180
170 155 164
3 12
  • Girlfriend #1 is already tall enough.
  • Girlfriend #2 can be gifted the second pair of shoes, increasing her height to 165 + 12 = 177.
  • Girlfriend #3 can be gifted the first pair of shoes, increasing her height to 164 + 3 = 167.

Sponsors Gold