BoB002-F: MIN of Pairs

2 secs 1024 MB
kyaneko999's icon kyaneko999

問題

11 から 2N2N までの番号がついた 2N2N 個の商品があり,商品 ii の価格は XiX_i です.
これらの商品を NN 組のペア Y1=(Y11,Y12)Y_1=(Y_{11},Y_{12})Y2=(Y21,Y22)Y_2=(Y_{21},Y_{22})\cdotsYN=(YN1,YN2)Y_N=(Y_{N1},Y_{N2}) に分割します.すなわち,以下が成り立ちます.

  • (Y11,Y12,Y21,Y22,,YN1,YN2)(Y_{11},Y_{12},Y_{21},Y_{22},\dots,Y_{N1},Y_{N2})(1,2,,2N)(1,2,\dots,2N) の並べ替えである.

各ペア Y1,Y2,,YNY_1,Y_2,\dots,Y_N について,順番に1回ずつ以下のような操作を行います.

  • ペアに含まれる2つの値を i,ji,j とする.Sakkyさんは,商品 ii と商品 jj のうち,より価格が安い方の商品を1つ購入する.
    ただし,価格が同じである場合には,商品 ii と商品 jj のうち,ランダムにいずれか1つを選び購入する.

最終的に,Sakkyさんは NN 個の商品を購入することになりますが,これらの合計金額が KK と等しくなるような Y1,Y2,,YNY_1,Y_2,\dots,Y_N の選び方は存在するでしょうか.

制約

  • 入力はすべて整数
  • 1N61\le N\le 6
  • 1K1091\le K\le 10^9
  • 1Xi1091\le X_i\le 10^9

入力

入力は以下の形式で標準入力から与えられる.

N  KN\;K
X1  X2    X2NX_1\;X_2\;\cdots\;X_{2N}

出力

条件を満たすような選び方が存在するならば Yes,そうでなければ No と出力しなさい.

入出力例

入力例1
3 7
1 2 3 4 5 6
出力例1
Yes

Y1=(1,3)Y_1=(1,3)Y2=(2,6)Y_2=(2,6)Y3=(4,5)Y_3=(4,5) と選べば,Sakkyさんが購入する商品の合計金額は 1+2+4=71+2+4=7 となります.
なお,この他にも条件をみたすような Y1,Y2,Y3Y_1,Y_2,Y_3 の選び方は存在します.

入力例2
1 2
1 2
出力例2
No

Y1=(1,2)Y_1=(1,2)Y1=(2,1)Y_1=(2,1) を選ぶことができますが,いずれの場合もSakkyさんが購入する商品の合計金額は 11 となり,K=2K=2 と等しくなることはありません.

入力例3
6 20
3 1 4 1 5 9 2 6 5 3 5 8
出力例3
Yes

Submit


Go (1.21)