У Дореми есть два массива целых чисел \(a\) и \(b\) из \(n\) целых чисел каждый, а также целое число \(k\).
Изначально у нее есть числовая прямая, где никакие точки не покрашены. Она выбирает перестановку \(p\) чисел \([1,2,\ldots,n]\), затем делает \(n\) ходов. На \(i\)-м ходу Дореми делает следующее:
- Она выбирает непокрашенное целое число \(x\) на числовой прямой, удовлетворяющее
- \(x \leq a_{p_i}\), или
- существует покрашенное целое число \(y\) такое, что \(y \leq a_{p_i}\) и \(x \leq y+b_{p_i}\).
- Она красит \(x\) в цвет \(p_i\).
Определите, может ли целое число \(k\) оказаться покрашенным в цвет \(1\).
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если точка \(k\) может оказаться покрашена в цвет \(1\). Иначе выведите «NO» (без кавычек).
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут приняты как положительны ответ).
Примечание
В первом примере невозможно покрасить число \(16\) в цвет \(1\).
Во втором примере \(p=[2,1,3,4]\) — одно из возможных решений, ниже показаны подробности.
- На первом ходу выбирается \(x=8\) и окрашивается в цвет \(2\), так как \(x=8\) еще не покрашено, и \(x \le a_2\).
- На втором ходу выбирается \(x=16\) и окрашивается в цвет \(1\), так как существует покрашенная точка \(y=8\) такая, что \(y\le a_1\) и \(x \le y + b_1\).
- На третьем ходу выбирается \(x=0\) и окрашивается в цвет \(3\), так как \(x=0\) еще не покрашено, и \(x \le a_3\).
- На четвертом ходу выбирается \(x=-2\) и окрашивается в цвет \(4\), так как \(x=-2\) еще не покрашено, и \(x \le a_4\).
- В итоге числа \(-2,0,8,16\) покрашены в цвета \(4,3,2,1\) соответственно.
В третьем примере одно из возможных решений — \(p=[2,1,4,3]\).
В четвертом примере одно из возможных решений — \(p=[2,3,4,1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4 16
5 3
8 12
10 7
15 1
4 16
8 12
10 7
15 1
5 3
4 16
10 7
15 1
5 3
8 12
4 16
15 1
5 3
8 12
10 7
1 1000000000
500000000 500000000
2 1000000000
1 999999999
1 1
|
NO
YES
YES
YES
NO
YES
|