Treasure
면접 대비시간 제한1초메모리 제한1024 MB
여러 데이터 세트에 대해 각 물건의 가치와 무게, 그리고 배낭 용량이 주어질 때 담을 수 있는 최대 가치 합을 구한다.
문제
After doing some digging on the beach, you happen to pull up an old treasure chest! It is full of rare artefacts worth a lot of money! Unfortunately, you can only carry so much with you back to your boat before the tide washes the treasure chest away. Write a program that will calculate the highest total item value that you can take back in one trip, given several item weights and values, and your carrying capacity.
입력
The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with two integers i w that indicate the number items that follow and your carrying capacity, respectively. The next i lines will each have two numbers, the value of each item and its weight.
출력
Output the highest value that you can carry in one trip for each data set.