시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 293 65 45 19.824%

문제

국제대학소포센터(ICPC: International Collegiate Parcel Center)는 전세계 대학생들을 대상으로 소포 무료 배송 이벤트를 진행하고 있다. 무료 배송 조건은 보낼 소포가 물품 4개로 구성되어야 하며 이들 물품의 무게 합이 정확히 정해진 정수 무게 w 그램이어야 한다는 것이다.

부산대학교에 있는 찬수는 영국 왕립대학에 있는 수환에게 보낼 물품이 매우 많이 있는데, 각 물품의 무게(모두 정수 그램)는 모두 다르다. 이 이벤트는 한시적으로 진행되는 이벤트이기 때문에 찬수는 자신이 보낼 물품 중에서 이 조건을 만족하는 물품 4개가 있는지 가능하면 빨리 알아내고 싶다. 다시 말해서 서로 다른 n(n ≥ 4)개의 정수로 이루어진 집합 A에서 4개의 원소만 꺼내어 만든 부분집합 B(|B| = 4)가 ∑bB b = w 조건을 만족하는지 판단하려고 한다. 

주어진 wA에 대해서, 위 조건을 만족하는 부분집합 B가 존재하면 YES를, 아니면 NO를 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 aiA(1 ≤ in)가 공백으로 분리되어 주어진다. 각 원소 ai는 1이상 200,000이하이다(1 ≤ ai ≤ 200,000).

출력

출력은 표준출력을 사용한다. 문제의 조건에 따라 YESNO를 한 줄에 출력한다.

예제 입력 1

10 6
5 10 7 3 2 1

예제 출력 1

NO

예제 입력 2

21 7
10 1 4 6 2 8 5

예제 출력 2

YES
W3sicHJvYmxlbV9pZCI6IjE2Mjg3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUGFyY2VsIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFkNmRcdWM4MWNcdWIzMDBcdWQ1NTlcdWMxOGNcdWQzZWNcdWMxM2NcdWQxMzAoSUNQQzogSW50ZXJuYXRpb25hbCBDb2xsZWdpYXRlIFBhcmNlbCBDZW50ZXIpXHViMjk0IFx1YzgwNFx1YzEzOFx1YWNjNCBcdWIzMDBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHViMzAwXHVjMGMxXHVjNzNjXHViODVjIFx1YzE4Y1x1ZDNlYyBcdWJiMzRcdWI4Y2MgXHViYzMwXHVjMWExIFx1Yzc3NFx1YmNhNFx1ZDJiOFx1Yjk3YyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWJiMzRcdWI4Y2MgXHViYzMwXHVjMWExIFx1Yzg3MFx1YWM3NFx1Yzc0MCBcdWJjZjRcdWIwYmMgXHVjMThjXHVkM2VjXHVhYzAwIFx1YmIzY1x1ZDQ4OCA0XHVhYzFjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAgXHVjNzc0XHViNGU0IFx1YmIzY1x1ZDQ4OFx1Yzc1OCBcdWJiMzRcdWFjOGMgXHVkNTY5XHVjNzc0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWM4MTVcdWQ1NzRcdWM5YzQgXHVjODE1XHVjMjE4IFx1YmIzNFx1YWM4YyA8ZW0+dzxcL2VtPiBcdWFkZjhcdWI3YThcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDgwXHVjMGIwXHViMzAwXHVkNTU5XHVhZDUwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNjMmNcdWMyMThcdWIyOTQgXHVjNjAxXHVhZDZkIFx1YzY1NVx1YjliZFx1YjMwMFx1ZDU1OVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVkNjU4XHVjNWQwXHVhYzhjIFx1YmNmNFx1YjBiYyBcdWJiM2NcdWQ0ODhcdWM3NzQgXHViOWU0XHVjNmIwIFx1YjljZVx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWMwMSBcdWJiM2NcdWQ0ODhcdWM3NTggXHViYjM0XHVhYzhjKFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMTggXHVhZGY4XHViN2E4KVx1YjI5NCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHViMmU0LiBcdWM3NzQgXHVjNzc0XHViY2E0XHVkMmI4XHViMjk0IFx1ZDU1Y1x1YzJkY1x1YzgwMVx1YzczY1x1Yjg1YyBcdWM5YzRcdWQ1ODlcdWI0MThcdWIyOTQgXHVjNzc0XHViY2E0XHVkMmI4XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWNjMmNcdWMyMThcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YmNmNFx1YjBiYyBcdWJiM2NcdWQ0ODggXHVjOTExXHVjNWQwXHVjMTFjIFx1Yzc3NCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmIzY1x1ZDQ4OCA0XHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzQgXHViZTY4XHViOWFjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YjJlNFx1YzJkYyBcdWI5ZDBcdWQ1NzRcdWMxMWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCA8ZW0+bjxcL2VtPig8ZW0+bjxcL2VtPiAmZ2U7IDQpXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjOWQxXHVkNTY5IDxlbT5BPFwvZW0+XHVjNWQwXHVjMTFjIDRcdWFjMWNcdWM3NTggXHVjNmQwXHVjMThjXHViOWNjIFx1YWViY1x1YjBiNFx1YzViNCBcdWI5Y2NcdWI0ZTAgXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5IDxlbT5CPFwvZW0+KHw8ZW0+QjxcL2VtPnwgPSA0KVx1YWMwMCAmc3VtOzxzdWI+PGVtPmI8XC9lbT4maXNpbjs8ZW0+QjxcL2VtPjxcL3N1Yj4gPGVtPmI8XC9lbT4gPSA8ZW0+dzxcL2VtPiBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0XHVjOWMwIFx1ZDMxMFx1YjJlOFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCA8ZW0+dzxcL2VtPlx1YzY0MCA8ZW0+QTxcL2VtPlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzcwNCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OSA8ZW0+QjxcL2VtPlx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzQgWUVTXHViOTdjLCBcdWM1NDRcdWIyYzhcdWJhNzQgTk9cdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwXHVjNzg1XHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM0XHVhYzhjIDxlbT53PFwvZW0+KDEwICZsZTsgPGVtPnc8XC9lbT4gJmxlOyA3OTksOTk0KVx1YzY0MCA8ZW0+QTxcL2VtPlx1Yzc1OCBcdWM2ZDBcdWMxOGMgXHVhYzFjXHVjMjE4IDxlbT5uPFwvZW0+KDQgJmxlOyA8ZW0+bjxcL2VtPiAmbGU7IDUsMDAwKVx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViZDg0XHViOWFjXHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCA8ZW0+QTxcL2VtPlx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWM3NzggPGVtPm48XC9lbT5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IDxlbT5hPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPjxcL3N1Yj4gJmlzaW47IDxlbT5BPFwvZW0+KDEgJmxlOyA8ZW0+aTxcL2VtPiAmbGU7IDxlbT5uPFwvZW0+KVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViZDg0XHViOWFjXHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzZkMFx1YzE4YyA8ZW0+YTxcL2VtPjxzdWI+PGVtPmk8XC9lbT48XC9zdWI+XHViMjk0IDFcdWM3NzRcdWMwYzEgMjAwLDAwMFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNCgxICZsZTsgPGVtPmE8XC9lbT48c3ViPjxlbT5pPFwvZW0+PFwvc3ViPiAmbGU7IDIwMCwwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWQ0NWNcdWM5MDBcdWNkOWNcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNWQwIFx1YjUzMFx1Yjc3YyA8Y29kZT5ZRVM8XC9jb2RlPlx1YjA5OCA8Y29kZT5OTzxcL2NvZGU+XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE2Mjg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGFyY2VsIiwiZGVzY3JpcHRpb24iOiI8cD5JQ1BDIChJbnRlcm5hdGlvbmFsIENvbGxlZ2lhdGUgUGFyY2VsIENlbnRlcikgaXMgbGVhZGluZyB0aGUgZXZlbnQgZm9yIGZyZWUgaW50ZXJuYXRpb25hbCBkZWxpdmVyeSBvZiBwYXJjZWxzIGFtb25nIHdvcmxkLXdpZGUgY29sbGVnaWF0ZSBzdHVkZW50cy4gVGhlIHJlcXVpcmVtZW50cyBmb3IgZnJlZSBkZWxpdmVyeSBhcmUgdGhhdCB0aGUgcGFyY2VsIHNob3VsZCBjb25zaXN0IG9mIGZvdXIgaXRlbXMgYW5kIHRoZSBzdW0gb2Ygd2VpZ2h0cyBvZiB0aGVtIHNob3VsZCBiZSBlcXVhbCB0byB0aGUgY2VydGFpbiBpbnRlZ3JhbCB3ZWlnaHQgPGVtPnc8XC9lbT4gZ3JhbS48XC9wPlxyXG5cclxuPHA+Q2hhbnNvbyBpbiBQdXNhbiBOYXRpb25hbCBVbml2ZXJzaXR5IGhhcyBhIGxvdCBvZiBpdGVtcyB0byBzZW5kIHRvIGhpcyBmcmllbmQgU29vd2hhbiBpbiBJbXBlcmlhbCBDb2xsZWdlIGluIExvbmRvbiwgYW5kIHRoZSB3ZWlnaHRzIG9mIHRoZSBpdGVtcyBhcmUgYWxsIGRpZmZlcmVudC4gU2luY2UgdGhpcyBpcyBhIGxpbWl0ZWQtdGltZSBldmVudCwgQ2hhbnNvbyB3YW50cyB0byBjaGVjayBhcyBmYXN0IGFzIHBvc3NpYmxlIHdoZXRoZXIgaGUgaGFzIGZvdXIgaXRlbXMgc2F0aXNmeWluZyB0byB0aGUgY29uZGl0aW9uIG9yIG5vdC4gQXNzdW1lIHRoYXQgdGhlIHdlaWdodHMgb2YgdGhlIGl0ZW1zIGFyZSBleGFjdCBwb3NpdGl2ZSBpbnRlZ2VyIGdyYW1zLCBhbmQgcmVtZW1iZXIgdGhleSBhcmUgYWxsIGRpc3RpbmN0LiBJbiBvdGhlciB3b3JkcywgQ2hhbnNvbyB3YW50cyB0byBzZWxlY3QgYSBzdWJzZXQgPGVtPkI8XC9lbT4gd2l0aCBmb3VyIGVsZW1lbnRzICh8PGVtPkI8XC9lbT58ID0gNCkgZnJvbSBhIHNldCA8ZW0+QTxcL2VtPiBvZiA8ZW0+bjxcL2VtPiAoPGVtPm48XC9lbT4gJmdlOyA0KSBkaXN0aW5jdCBwb3NpdGl2ZSBpbnRlZ2VycywgYW5kIHdhbnRzIHRvIGNoZWNrIHdoZXRoZXIgJnN1bTs8c3ViPjxlbT5iPFwvZW0+JmlzaW47PGVtPkI8XC9lbT48XC9zdWI+IDxlbT5iPFwvZW0+ID0gPGVtPnc8XC9lbT4gb3Igbm90LjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHRhcmdldCB3ZWlnaHQgPGVtPnc8XC9lbT4gYW5kIGEgc2V0IDxlbT5BPFwvZW0+IG9mIDxlbT5uPFwvZW0+IGRpc3RpbmN0IHBvc2l0aXZlIGludGVnZXJzLCB3cml0ZSBhIHByb2dyYW0gdG8gcHJpbnQgPGNvZGU+WUVTPFwvY29kZT4gaWYgc3VjaCBzdWJzZXQgPGVtPkI8XC9lbT4gZXhpc3RzLCBhbmQgPGNvZGU+Tk88XC9jb2RlPiwgb3RoZXJ3aXNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyA8ZW0+dzxcL2VtPiBhbmQgPGVtPm48XC9lbT4gc2VwYXJhdGVkIGJ5IGEgc3BhY2UsIHdoZXJlIDxlbT53PFwvZW0+ICgxMCAmbGU7IDxlbT53PFwvZW0+ICZsZTsgNzk5LDk5NCkgaXMgdGhlIHRhcmdldCB3ZWlnaHQgYW5kIDxlbT5uPFwvZW0+ICg0ICZsZTsgPGVtPm48XC9lbT4gJmxlOyA1LDAwMCksIHRoZSBudW1iZXIgb2YgZWxlbWVudHMgb2YgPGVtPkE8XC9lbT4uIEluIHRoZSBmb2xsb3dpbmcgbGluZSwgPGVtPm48XC9lbT4gcG9zaXRpdmUgaW50ZWdlcnMsIDxlbT5hPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPjxcL3N1Yj4gJmlzaW47IDxlbT5BPFwvZW0+ICgxICZsZTsgPGVtPmk8XC9lbT4gJmxlOyA8ZW0+bjxcL2VtPiksIGFyZSBnaXZlbiBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gRWFjaCBlbGVtZW50IDxlbT5hPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPjxcL3N1Yj4gaXMgaW4gdGhlIHJhbmdlIG9mIDEgYW5kIDIwMCwwMDAgaW5jbHVzaXZlbHkgKDEgJmxlOyA8ZW0+YTxcL2VtPjxzdWI+PGVtPmk8XC9lbT48XC9zdWI+ICZsZTsgMjAwLDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSB3aGljaCBjb250YWlucyA8Y29kZT5ZRVM8XC9jb2RlPiBvciA8Y29kZT5OTzxcL2NvZGU+IGFjY29yZGluZyB0byB0aGUgcmVxdWlyZW1lbnRzIGFib3ZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==