시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 528 192 143 38.649%

문제

더운 여름날 동물원의 백곰 앨버트는 너무 더워서 꼼짝도 하기 싫다. 다행히도 사육사들이 앨버트의 더위를 식히기 위해 얼음이 담긴 양동이들을 가져다 주었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자.

우리 안은 1차원 배열로 생각하며, 총 N(1 ≤ N ≤ 100000)개의 얼음 양동이들이 xi(0 ≤ xi ≤ 1,000,000)좌표마다 놓여 있고 각 양동이 안에는 gi(1 ≤ gi ≤ 10,000)씩의 얼음이 들어 있다. 일단 앨버트가 자리를 잡으면 그로부터 좌우로 K(1 ≤ K ≤ 2,000,000) 만큼 떨어진 양동이까지 닿을 수 있다. 앨버트는 양동이가 놓여 있는 자리에도 자리잡을 수 있다. 모든 얼음 양동이의 위치는 다르다.

앨버트가 최적의 자리를 골랐을 때 얼음의 합을 구하시오. 즉, 얼음들의 합의 최댓값을 구해야 한다.

입력

첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다.

출력

앨버트가 택한 최적 위치로부터 K만큼 떨어진 거리 내에 있는 얼음들의 합(최댓값)을 출력한다.

예제 입력 1

4 3
4 7
10 15
2 2
5 1

예제 출력 1

11

힌트

앨버트가 x=4에 자리를 잡으면 x=1, x=2, x=7에 있는 얼음 양동이에 닿을 수 있다.

W3sicHJvYmxlbV9pZCI6IjEwMDI1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzhjXHVjNzNjXHViOTc4IFx1YmMzMVx1YWNmMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMzU0XHVjNmI0IFx1YzVlY1x1Yjk4NFx1YjBhMCBcdWIzZDlcdWJiM2NcdWM2ZDBcdWM3NTggXHViYzMxXHVhY2YwIFx1YzU2OFx1YmM4NFx1ZDJiOFx1YjI5NCBcdWIxMDhcdWJiMzQgXHViMzU0XHVjNmNjXHVjMTFjIFx1YWYzY1x1YzlkZFx1YjNjNCBcdWQ1NThcdWFlMzAgXHVjMmViXHViMmU0LiZuYnNwO1x1YjJlNFx1ZDU4OVx1ZDc4OFx1YjNjNCBcdWMwYWNcdWM3MjFcdWMwYWNcdWI0ZTRcdWM3NzQgXHVjNTY4XHViYzg0XHVkMmI4XHVjNzU4IFx1YjM1NFx1YzcwNFx1Yjk3YyBcdWMyZGRcdWQ3ODhcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzViY1x1Yzc0Y1x1Yzc3NCBcdWIyZjRcdWFlMzQgXHVjNTkxXHViM2Q5XHVjNzc0XHViNGU0XHVjNzQ0IFx1YWMwMFx1YzgzOFx1YjJlNCBcdWM4ZmNcdWM1YzhcdWIyZTQuJm5ic3A7XHVjNTY4XHViYzg0XHVkMmI4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVhYzcwXHViOWFjXHViOWNjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YWNlMFx1YjNjNCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YzViY1x1Yzc0Y1x1YzczY1x1Yjg1YyBcdWIzNTRcdWM3MDRcdWI5N2MgXHVjMmRkXHVkNzkwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWMgXHVjNTQ4XHVjNzQwIDFcdWNjMjhcdWM2ZDAgXHViYzMwXHVjNWY0XHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3MCwgXHVjZDFkIE4oMSAmbGU7IE4gJmxlOyAxMDAwMDApXHVhYzFjXHVjNzU4IFx1YzViY1x1Yzc0YyBcdWM1OTFcdWIzZDlcdWM3NzRcdWI0ZTRcdWM3NzQgeDxzdWI+aTxcL3N1Yj4oMCAmbGU7IHg8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyAxLDAwMCwwMDApXHVjODhjXHVkNDVjXHViOWM4XHViMmU0IFx1YjE5M1x1YzVlYyBcdWM3ODhcdWFjZTAmbmJzcDtcdWFjMDEgXHVjNTkxXHViM2Q5XHVjNzc0IFx1YzU0OFx1YzVkMFx1YjI5NCBnPHN1Yj5pPFwvc3ViPigxICZsZTsgZzxzdWI+aTxcL3N1Yj4gJmxlOyAxMCwwMDApXHVjNTI5XHVjNzU4IFx1YzViY1x1Yzc0Y1x1Yzc3NCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMmU0LiZuYnNwO1x1Yzc3Y1x1YjJlOCBcdWM1NjhcdWJjODRcdWQyYjhcdWFjMDAgXHVjNzkwXHViOWFjXHViOTdjIFx1YzdhMVx1YzczY1x1YmE3NCBcdWFkZjhcdWI4NWNcdWJkODBcdWQxMzAgXHVjODhjXHVjNmIwXHViODVjIEsoMSAmbGU7Jm5ic3A7SyAmbGU7IDIsMDAwLDAwMCkgXHViOWNjXHVkMDdjIFx1YjVhOFx1YzViNFx1YzljNCBcdWM1OTFcdWIzZDlcdWM3NzRcdWFlNGNcdWM5YzAgXHViMmZmXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzU2OFx1YmM4NFx1ZDJiOFx1YjI5NCBcdWM1OTFcdWIzZDlcdWM3NzRcdWFjMDAgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWI5YWNcdWM1ZDBcdWIzYzQgXHVjNzkwXHViOWFjXHVjN2ExXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM1YmNcdWM3NGMgXHVjNTkxXHViM2Q5XHVjNzc0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU2OFx1YmM4NFx1ZDJiOFx1YWMwMCBcdWNkNWNcdWM4MDFcdWM3NTggXHVjNzkwXHViOWFjXHViOTdjIFx1YWNlOFx1Yjc5MFx1Yzc0NCBcdWI1NGMgXHVjNWJjXHVjNzRjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Yzk4OSwgXHVjNWJjXHVjNzRjXHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IE5cdWFjZmMgS1x1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuJm5ic3A7XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCwgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVhYzAxIFx1YzU5MVx1YjNkOVx1Yzc3NFx1Yzc1OCBcdWM1YmNcdWM3NGNcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBnPHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWM1OTFcdWIzZDlcdWM3NzRcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCB4PHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNTY4XHViYzg0XHVkMmI4XHVhYzAwIFx1ZDBkZFx1ZDU1YyBcdWNkNWNcdWM4MDEgXHVjNzA0XHVjZTU4XHViODVjXHViZDgwXHVkMTMwIEtcdWI5Y2NcdWQwN2MgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWM3MFx1YjlhYyBcdWIwYjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzViY1x1Yzc0Y1x1YjRlNFx1Yzc1OCBcdWQ1NjkoXHVjZDVjXHViMzEzXHVhYzEyKVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzU2OFx1YmM4NFx1ZDJiOFx1YWMwMCZuYnNwO3g9NFx1YzVkMCBcdWM3OTBcdWI5YWNcdWI5N2MgXHVjN2ExXHVjNzNjXHViYTc0IHg9MSwgeD0yLCB4PTdcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzViY1x1Yzc0YyBcdWM1OTFcdWIzZDlcdWM3NzRcdWM1ZDAgXHViMmZmXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDAyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBMYXp5IENvdyIsImRlc2NyaXB0aW9uIjoiPHA+SXQmYXBvcztzIGEgaG90IHN1bW1lciBkYXksIGFuZCBCZXNzaWUgdGhlIGNvdyBpcyBmZWVsaW5nIHF1aXRlIGxhenkuICBTaGUgd2FudHMgdG8gbG9jYXRlIGhlcnNlbGYgYXQgYSBwb3NpdGlvbiBpbiBoZXIgZmllbGQgc28gdGhhdCBzaGUgY2FuIHJlYWNoIGFzIG11Y2ggZGVsaWNpb3VzIGdyYXNzIGFzIHBvc3NpYmxlIHdpdGhpbiBvbmx5IGEgc2hvcnQgZGlzdGFuY2UuPFwvcD48cD5UaGVyZSBhcmUgTiBwYXRjaGVzIG9mIGdyYXNzICgxICZsdDs9IE4gJmx0Oz0gMTAwLDAwMCkgaW4gQmVzc2llJmFwb3M7cyBmaWVsZCwgd2hpY2ggd2UgY2FuIHRoaW5rIG9mIGFzIGEgbG9uZyBvbmUtZGltZW5zaW9uYWwgbnVtYmVyIGxpbmUuICBUaGUgaXRoIHN1Y2ggcGF0Y2ggY29udGFpbnMgZ19pIHVuaXRzIG9mIGdyYXNzICgxICZsdDs9IGdfaSAmbHQ7PSAxMCwwMDApIGFuZCBpcyBsb2NhdGVkIGF0IGEgZGlzdGluY3QgcG9pbnQgeF9pIGFsb25nIHRoZSBmaWVsZCAoMCAmbHQ7PSB4X2kgJmx0Oz0gMSwwMDAsMDAwKS4gIEJlc3NpZSB3b3VsZCBsaWtlIHRvIGNob29zZSBhIHBvaW50IGluIHRoZSBmaWVsZCBhcyBoZXIgaW5pdGlhbCBsb2NhdGlvbiAocG9zc2libHkgdGhlIHNhbWUgcG9pbnQgYXMgYSBwYXRjaCBvZiBncmFzcykgc28gdGhhdCBhIG1heGltdW0gYW1vdW50IG9mIGdyYXNzIGlzIHdpdGhpbiBhIGRpc3RhbmNlIG9mIEsgc3RlcHMgZnJvbSB0aGlzIGxvY2F0aW9uICgxICZsdDs9IEsgJmx0Oz0gMiwwMDAsMDAwKS48XC9wPjxwPlBsZWFzZSBoZWxwIEJlc3NpZSBkZXRlcm1pbmUgdGhlIG1heGltdW0gYW1vdW50IG9mIGdyYXNzIHNoZSBjYW4gcmVhY2gsIGlmIHNoZSBjaG9vc2VzIHRoZSBiZXN0IHBvc3NpYmxlIGluaXRpYWwgbG9jYXRpb24uPFwvcD4iLCJpbnB1dCI6Ijx1bD48bGk+TGluZSAxOiBUd28gaW50ZWdlcnMgTiBhbmQgSy48XC9saT48bGk+TGluZXMgMi4uMStOOiBMaW5lIGkrMSBkZXNjcmliZXMgdGhlIGl0aCBwYXRjaCBvZiBncmFzcyB1c2luZyAyIGludGVnZXJzOiBnX2kgYW5kIHhfaTxcL2xpPjxcL3VsPiIsIm91dHB1dCI6Ijx1bD48bGk+TGluZSAxOiBUaGUgbWF4aW11bSBhbW91bnQgb2YgZ3Jhc3Mgd2l0aGluIGRpc3RhbmNlIEsgb2YgQmVzc2llJmFwb3M7cyBvcHRpbWFsIGxvY2F0aW9uLjxcL2xpPjxcL3VsPiIsImhpbnQiOiI8aDQ+T3V0cHV0IERldGFpbHM8XC9oND48cD5CZXNzaWUgc2hvdWxkIGxvY2F0ZSBoZXJzZWxmIGF0IHBvc2l0aW9uIHg9NCwgc28gdGhlIGdyYXNzIGF0IHBvc2l0aW9ucyB4PTEsIHg9MiwgYW5kIHg9NyBpcyBhbGwgd2l0aGluIGhlciByZWFjaC48XC9wPiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2013-2014 Season > USACO March 2014 Contest > Bronze 2번

  • 문제를 번역한 사람: pjw
  • 잘못된 번역을 찾은 사람: swh98