시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 172 64 40 38.835%

문제

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

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

앨버트가 최적의 자리를 골랐을 때 얼음의 합을 구하시오.(즉, 얼음들의 합의 최대값을 구하시오.)

입력

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

출력

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

예제 입력 1

4 3
4 7
10 15
2 2
5 1

예제 출력 1

11

힌트

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

W3sicHJvYmxlbV9pZCI6IjEwMDI1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzhjXHVjNzNjXHViOTc4IFx1YmMzMVx1YWNmMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMzU0XHVjNmI0IFx1YzVlY1x1Yjk4NFx1YjBhMCBcdWIzZDlcdWJiM2NcdWM2ZDBcdWM3NTggXHViYzMxXHVhY2YwIFx1YzU2OFx1YmM4NFx1ZDJiOFx1YjI5NCBcdWIxMDhcdWJiMzQgXHViMzU0XHVjNmNjXHVjMTFjIFx1YWYzY1x1YzlkZFx1YjNjNCBcdWQ1NThcdWFlMzAgXHVjMmViXHViMmU0LiZuYnNwO1x1YjJlNFx1ZDU4OVx1ZDc4OFx1YjNjNCBcdWMwYWNcdWM3MjFcdWMwYWNcdWI0ZTRcdWM3NzQgXHVjNTY4XHViYzg0XHVkMmI4XHVjNzU4IFx1YjM1NFx1YzcwNFx1Yjk3YyBcdWMyZGRcdWQ3ODhcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzViY1x1Yzc0Y1x1Yzc3NCBcdWIyZjRcdWFlMzQgXHVjNTkxXHViM2Q5XHVjNzc0XHViNGU0XHVjNzQ0IFx1YWMwMFx1YzgzOFx1YjJlNCBcdWM4ZmNcdWM1YzhcdWIyZTQuJm5ic3A7XHVjNTY4XHViYzg0XHVkMmI4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVhYzcwXHViOWFjXHViOWNjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YWNlMFx1YjNjNCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YzViY1x1Yzc0Y1x1YzczY1x1Yjg1YyBcdWIzNTRcdWM3MDRcdWI5N2MgXHVjMmRkXHVkNzkwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWMgXHVjNTQ4XHVjNzQwIDFcdWNjMjhcdWM2ZDAgXHViYzMwXHVjNWY0XHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3MCwgXHVjZDFkIE4oMSZsdDs9TiZsdDs9MTAwMDAwKVx1YWMxY1x1Yzc1OCBcdWM1YmNcdWM3NGMgXHVjNTkxXHViM2Q5XHVjNzc0XHViNGU0XHVjNzc0IHhfaSgwJmx0Oz14X2kmbHQ7PTEsMDAwLDAwMClcdWM4OGNcdWQ0NWNcdWI5YzhcdWIyZTQgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YWNlMCZuYnNwO1x1YWMwMSBcdWM1OTFcdWIzZDlcdWM3NzQgXHVjNTQ4XHVjNWQwXHViMjk0IGdfaSgxICZsdDs9IGdfaSAmbHQ7PSAxMCwwMDApXHVjNTI5XHVjNzU4IFx1YzViY1x1Yzc0Y1x1Yzc3NCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMmU0LiZuYnNwO1x1Yzc3Y1x1YjJlOCBcdWM1NjhcdWJjODRcdWQyYjhcdWFjMDAgXHVjNzkwXHViOWFjXHViOTdjIFx1YzdhMVx1YzczY1x1YmE3NCBcdWFkZjhcdWI4NWNcdWJkODBcdWQxMzAgXHVjODhjXHVjNmIwXHViODVjIEsoMSAmbHQ7PSBLICZsdDs9IDIsMDAwLDAwMCkgXHViOWNjXHVkMDdjIFx1YjVhOFx1YzViNFx1YzljNCBcdWM1OTFcdWIzZDlcdWM3NzRcdWFlNGNcdWM5YzAgXHViMmZmXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM1NjhcdWJjODRcdWQyYjhcdWIyOTQgXHVjNTkxXHViM2Q5XHVjNzc0XHVhYzAwIFx1YjE5M1x1YzVlYyBcdWM3ODhcdWIyOTQgXHVjNzkwXHViOWFjXHVjNWQwXHViM2M0IFx1Yzc5MFx1YjlhY1x1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzRjKTxcL3A+XHJcblxyXG48cD5cdWM1NjhcdWJjODRcdWQyYjhcdWFjMDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWFjZThcdWI3OTBcdWM3NDQgXHViNTRjIFx1YzViY1x1Yzc0Y1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LihcdWM5ODksIFx1YzViY1x1Yzc0Y1x1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC4pPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOXHVhY2ZjIEtcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiZuYnNwO1x1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAsIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YWMwMSBcdWM1OTFcdWIzZDlcdWM3NzRcdWM3NTggXHVjNWJjXHVjNzRjXHVjNzU4IFx1YzU5MVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgZ19pXHVjNjQwIFx1YzU5MVx1YjNkOVx1Yzc3NFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IHhfaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNTY4XHViYzg0XHVkMmI4XHVhYzAwIFx1ZDBkZFx1ZDU1YyBcdWNkNWNcdWM4MDEgXHVjNzA0XHVjZTU4XHViODVjXHViZDgwXHVkMTMwIEtcdWI5Y2NcdWQwN2MgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWM3MFx1YjlhYyBcdWIwYjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzViY1x1Yzc0Y1x1YjRlNFx1Yzc1OCBcdWQ1NjkoXHVjZDVjXHViMzAwXHVhYzEyKTxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM1NjhcdWJjODRcdWQyYjhcdWFjMDAmbmJzcDt4PTRcdWM1ZDAgXHVjNzkwXHViOWFjXHViOTdjIFx1YzdhMVx1YzczY1x1YmE3NCB4PTEsIHg9MiwgeD03XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM1YmNcdWM3NGMgXHVjNTkxXHViM2Q5XHVjNzc0XHVjNWQwIFx1YjJmZlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAwMjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgTGF6eSBDb3ciLCJkZXNjcmlwdGlvbiI6IjxwPkl0JmFwb3M7cyBhIGhvdCBzdW1tZXIgZGF5LCBhbmQgQmVzc2llIHRoZSBjb3cgaXMgZmVlbGluZyBxdWl0ZSBsYXp5LiAgU2hlIHdhbnRzIHRvIGxvY2F0ZSBoZXJzZWxmIGF0IGEgcG9zaXRpb24gaW4gaGVyIGZpZWxkIHNvIHRoYXQgc2hlIGNhbiByZWFjaCBhcyBtdWNoIGRlbGljaW91cyBncmFzcyBhcyBwb3NzaWJsZSB3aXRoaW4gb25seSBhIHNob3J0IGRpc3RhbmNlLjxcL3A+PHA+VGhlcmUgYXJlIE4gcGF0Y2hlcyBvZiBncmFzcyAoMSAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIGluIEJlc3NpZSZhcG9zO3MgZmllbGQsIHdoaWNoIHdlIGNhbiB0aGluayBvZiBhcyBhIGxvbmcgb25lLWRpbWVuc2lvbmFsIG51bWJlciBsaW5lLiAgVGhlIGl0aCBzdWNoIHBhdGNoIGNvbnRhaW5zIGdfaSB1bml0cyBvZiBncmFzcyAoMSAmbHQ7PSBnX2kgJmx0Oz0gMTAsMDAwKSBhbmQgaXMgbG9jYXRlZCBhdCBhIGRpc3RpbmN0IHBvaW50IHhfaSBhbG9uZyB0aGUgZmllbGQgKDAgJmx0Oz0geF9pICZsdDs9IDEsMDAwLDAwMCkuICBCZXNzaWUgd291bGQgbGlrZSB0byBjaG9vc2UgYSBwb2ludCBpbiB0aGUgZmllbGQgYXMgaGVyIGluaXRpYWwgbG9jYXRpb24gKHBvc3NpYmx5IHRoZSBzYW1lIHBvaW50IGFzIGEgcGF0Y2ggb2YgZ3Jhc3MpIHNvIHRoYXQgYSBtYXhpbXVtIGFtb3VudCBvZiBncmFzcyBpcyB3aXRoaW4gYSBkaXN0YW5jZSBvZiBLIHN0ZXBzIGZyb20gdGhpcyBsb2NhdGlvbiAoMSAmbHQ7PSBLICZsdDs9IDIsMDAwLDAwMCkuPFwvcD48cD5QbGVhc2UgaGVscCBCZXNzaWUgZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIGFtb3VudCBvZiBncmFzcyBzaGUgY2FuIHJlYWNoLCBpZiBzaGUgY2hvb3NlcyB0aGUgYmVzdCBwb3NzaWJsZSBpbml0aWFsIGxvY2F0aW9uLjxcL3A+IiwiaW5wdXQiOiI8dWw+PGxpPkxpbmUgMTogVHdvIGludGVnZXJzIE4gYW5kIEsuPFwvbGk+PGxpPkxpbmVzIDIuLjErTjogTGluZSBpKzEgZGVzY3JpYmVzIHRoZSBpdGggcGF0Y2ggb2YgZ3Jhc3MgdXNpbmcgMiBpbnRlZ2VyczogZ19pIGFuZCB4X2k8XC9saT48XC91bD4iLCJvdXRwdXQiOiI8dWw+PGxpPkxpbmUgMTogVGhlIG1heGltdW0gYW1vdW50IG9mIGdyYXNzIHdpdGhpbiBkaXN0YW5jZSBLIG9mIEJlc3NpZSZhcG9zO3Mgb3B0aW1hbCBsb2NhdGlvbi48XC9saT48XC91bD4iLCJoaW50IjoiPGg0Pk91dHB1dCBEZXRhaWxzPFwvaDQ+PHA+QmVzc2llIHNob3VsZCBsb2NhdGUgaGVyc2VsZiBhdCBwb3NpdGlvbiB4PTQsIHNvIHRoZSBncmFzcyBhdCBwb3NpdGlvbnMgeD0xLCB4PTIsIGFuZCB4PTcgaXMgYWxsIHdpdGhpbiBoZXIgcmVhY2guPFwvcD4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==