구름이는 이상한 느낌이 들어 잠에서 깼습니다. 잠에서 깨어 정신을 차려보니 건물에 화재가 발생해서 신속하게 빠져나가야만 합니다.

그런 구름이 눈에 가방하나가 눈에 띄었는데 이 가방은 정해진 무게 이상을 담으면 찢어지기 때문에 한계 무게 미만으로 담아야합니다.

건물 밖으로 대피하면 다시는 돌아올 수 없기 때문에 구름이는 보이는 물건들을 가방의 적재량에 맞으면서도 가장 값어치가 높도록 챙겨서 나가고 싶어합니다.

구름이가 가장 큰 값어치 만큼의 물건들을 가지고 대피할 수 있도록 하는 프로그램을 작성하십시오.

입력

첫째 줄에 물건의 개수

물건의 개수 만큼 무게, 값어치 순으로 입력 (최대 20개)

가방의 최대 적재량

출력

가방에 적재한 물건(들)의 최대 값어치