시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 69 44 40 68.966%

문제

한 농부가 할로윈 파티에 그의 소들을 데려가려고한다. 아쉽게도 농부에게는 코스튬이 한벌밖에 없다. 그 코스튬에는 정확하게 사이즈는 S(1 <= S <= 1,000,000)이며, 최대 소 두마리가 들어간다. 농부는 N(2 <= N <= 20,000)마리의 소가 있으며(소의 이름은 편의상 소1.. 소N으로한다), 소i의 사이즈는 (1 <= L_i <= 1,000,000)이다. 만약 소 두마리의 크기 합이 코스튬의 크기 이하인 경우 둘이 코스튬에 들어갈 수 있다. 농부가 코스튬에 얼마나 많은 서로 다른 소의 짝이 들어가는지 구할수있도록 도와주자.

입력

첫째 줄에는 정수 N(소의 수)과 S(코스튬의 크기)가 주어진다.

둘째 줄부터는 각 줄에 소들의 크기가 주어진다.

출력

첫째 줄에 얼마나 많은 짝이 가능한지 출력한다.

예제 입력 1

4 6
3
5
2
1

예제 출력 1

4

힌트

위의 문제에서 4개의 짝은 아래와 같다.

  • 소1-소3 (사이즈 합:5)
  • 소1-소4 (사이즈 합:4)
  • 소2-소4 (사이즈 합:6)
  • 소3-소4 (사이즈 합:3)
W3sicHJvYmxlbV9pZCI6IjYxNTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWMyYTRcdWQyYWMgXHVkMzBjXHVkMmYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NWMgXHViMThkXHViZDgwXHVhYzAwIFx1ZDU2MFx1Yjg1Y1x1YzcwOCBcdWQzMGNcdWQyZjBcdWM1ZDAgXHVhZGY4XHVjNzU4IFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWIzNzBcdWI4MjRcdWFjMDBcdWI4MjRcdWFjZTBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1YzI3ZFx1YWM4Y1x1YjNjNCBcdWIxOGRcdWJkODBcdWM1ZDBcdWFjOGNcdWIyOTQgXHVjZjU0XHVjMmE0XHVkMmFjXHVjNzc0IFx1ZDU1Y1x1YmM4Y1x1YmMxNlx1YzVkMCBcdWM1YzZcdWIyZTQuIFx1YWRmOCBcdWNmNTRcdWMyYTRcdWQyYWNcdWM1ZDBcdWIyOTQgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1YzBhY1x1Yzc3NFx1Yzk4OFx1YjI5NCBTKDEgJmx0Oz0gUyAmbHQ7PSAxLDAwMCwwMDApXHVjNzc0XHViYTcwLCBcdWNkNWNcdWIzMDAmbmJzcDtcdWMxOGMgXHViNDUwXHViOWM4XHViOWFjXHVhYzAwIFx1YjRlNFx1YzViNFx1YWMwNFx1YjJlNC4gXHViMThkXHViZDgwXHViMjk0IE4oMiAmbHQ7PSBOICZsdDs9IDIwLDAwMClcdWI5YzhcdWI5YWNcdWM3NTggXHVjMThjXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MChcdWMxOGNcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIFx1ZDNiOFx1Yzc1OFx1YzBjMSBcdWMxOGMxLi4gXHVjMThjTlx1YzczY1x1Yjg1Y1x1ZDU1Y1x1YjJlNCksJm5ic3A7XHVjMThjaVx1Yzc1OCBcdWMwYWNcdWM3NzRcdWM5ODhcdWIyOTQmbmJzcDsoMSAmbHQ7PSBMX2kgJmx0Oz0gMSwwMDAsMDAwKVx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzE4YyBcdWI0NTBcdWI5YzhcdWI5YWNcdWM3NTggXHVkMDZjXHVhZTMwIFx1ZDU2OVx1Yzc3NCBcdWNmNTRcdWMyYTRcdWQyYWNcdWM3NTggXHVkMDZjXHVhZTMwIFx1Yzc3NFx1ZDU1OFx1Yzc3OCBcdWFjYmRcdWM2YjAgXHViNDU4XHVjNzc0IFx1Y2Y1NFx1YzJhNFx1ZDJhY1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViMThkXHViZDgwXHVhYzAwIFx1Y2Y1NFx1YzJhNFx1ZDJhY1x1YzVkMCBcdWM1YmNcdWI5YzhcdWIwOTggXHViOWNlXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMThjXHVjNzU4IFx1YzlkZFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTYwXHVjMjE4XHVjNzg4XHViM2M0XHViODVkIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IE4oXHVjMThjXHVjNzU4IFx1YzIxOClcdWFjZmMgUyhcdWNmNTRcdWMyYTRcdWQyYWNcdWM3NTggXHVkMDZjXHVhZTMwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzBcdWIyOTQgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWMxOGNcdWI0ZTRcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzViY1x1YjljOFx1YjA5OCBcdWI5Y2VcdWM3NDAgXHVjOWRkXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzcwNFx1Yzc1OCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgNFx1YWMxY1x1Yzc1OCBcdWM5ZGRcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWMxOGMxLVx1YzE4YzMgKFx1YzBhY1x1Yzc3NFx1Yzk4OCBcdWQ1Njk6NSk8XC9saT5cclxuXHQ8bGk+XHVjMThjMS1cdWMxOGM0Jm5ic3A7KFx1YzBhY1x1Yzc3NFx1Yzk4OCBcdWQ1Njk6NCk8XC9saT5cclxuXHQ8bGk+XHVjMThjMi1cdWMxOGM0Jm5ic3A7KFx1YzBhY1x1Yzc3NFx1Yzk4OCBcdWQ1Njk6Nik8XC9saT5cclxuXHQ8bGk+XHVjMThjMy1cdWMxOGM0Jm5ic3A7KFx1YzBhY1x1Yzc3NFx1Yzk4OCBcdWQ1Njk6Myk8XC9saT5cclxuPFwvdWw+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjE1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvc3R1bWUgUGFydHkiLCJkZXNjcmlwdGlvbiI6IjxwPkl0JiMzOTtzIEhhbGxvd2VlbiEgRmFybWVyIEpvaG4gaXMgdGFraW5nIHRoZSBjb3dzIHRvIGEgY29zdHVtZSBwYXJ0eSwgYnV0IHVuZm9ydHVuYXRlbHkgaGUgb25seSBoYXMgb25lIGNvc3R1bWUuIFRoZSBjb3N0dW1lIGZpdHMgcHJlY2lzZWx5IHR3byBjb3dzIHdpdGggYSBsZW5ndGggb2YgUyAoMSAmbHQ7PSBTICZsdDs9IDEsMDAwLDAwMCkuIEZKIGhhcyBOIGNvd3MgKDIgJmx0Oz0gTiAmbHQ7PSAyMCwwMDApIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OOyBjb3cgaSBoYXMgbGVuZ3RoIExfaSAoMSAmbHQ7PSBMX2kgJmx0Oz0gMSwwMDAsMDAwKS4gVHdvIGNvd3MgY2FuIGZpdCBpbnRvIHRoZSBjb3N0dW1lIGlmIHRoZSBzdW0gb2YgdGhlaXIgbGVuZ3RocyBpcyBubyBncmVhdGVyIHRoYW4gdGhlIGxlbmd0aCBvZiB0aGUgY29zdHVtZS4gRkogd2FudHMgdG8ga25vdyBob3cgbWFueSBwYWlycyBvZiB0d28gZGlzdGluY3QgY293cyB3aWxsIGZpdCBpbnRvIHRoZSBjb3N0dW1lLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBTPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlcjogTF9pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgY293cyBGSiBjYW4gY2hvb3NlLiBOb3RlIHRoYXQgdGhlIG9yZGVyIG9mIHRoZSB0d28gY293cyBkb2VzIG5vdCBtYXR0ZXIuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBmb3VyIHBhaXJzIGFyZSBhcyBmb2xsb3dzOiBjb3cgMSBhbmQgY293IDM7IGNvdyAxIGFuZCBjb3cgNDsgY293IDIgYW5kIGNvdyA0OyBhbmQgZmluYWxseSBjb3cgMyBhbmQgY293IDQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO January 2008 Contest > Bronze 1번