생일 선물
면접 대비시간 제한2초메모리 제한512 MB
가격 차이가 D보다 작은 선물들을 골라 만족도의 합을 최대로 만든다.
문제
오늘은 강민이의 생일이다. 강민이에게는 친구 N명이 있고, 친구마다 강민이를 위한 생일 선물을 하나씩 준비했다. 선물에는 가격 P와 만족도 V가 있다. P는 그 선물의 가격이고, V는 강민이가 그 선물을 받았을 때 기뻐하는 정도를 수치로 나타낸 값이다.
강민이는 선물을 모두 받고 싶다. 그런데 어떤 친구가 준 선물의 가격이 다른 친구가 준 선물의 가격과 D 이상 차이 나면, 더 싼 선물을 준 친구가 미안함을 느낄 수 있다. 강민이는 자기 행복도 중요하지만 생일 선물 때문에 친구가 미안해하는 것은 원하지 않는다. 그래서 고심 끝에 일부 친구에게만 선물을 받기로 했다.
아무도 미안해하지 않도록 선물을 골라 받을 때, 강민이가 느끼는 만족도의 합이 최대 얼마인지 구하라. 받기로 한 선물 중 가장 비싼 선물과 가장 싼 선물의 가격 차이가 D보다 작으면 아무도 미안해하지 않는다.
입력
첫째 줄에 친구의 수 N과, 친구가 미안함을 느끼게 되는 최소 가격 차이 D가 주어진다. (, )
둘째 줄부터 N개 줄에 선물의 가격 P와 만족도 V가 한 줄에 하나씩 주어진다. (, )
출력
첫째 줄에 강민이가 느낄 수 있는 만족도의 최대 합을 출력한다.