Exercise available on https://www.beecrowd.com.br/judge/pt/problems/view/1624

Goal: Use Knapsack Problem

Input: The input consists of T test cases. Each test case starts with an integer N (1 ≤ N ≤ 100) that indicates the number of products in the list L . The next N lines are formed by 2 integers p and P . The first integer, p (1 ≤ p ≤ 1000), represents the price of the product. The second integer P ,(1 ≤ P ≤ 30) represents the weight of the product. The next line contains an integer M , which indicates the maximum weight allowed. The end of the input is represented by a 0.

Exit: For each test case, print an integer that represents the total number of products that Dr Luis Cláudio is able to take home.