題目描述

現在一共有若干項貨品可選擇運載，每一項 k 都有一個已知的 體積 v[k]，以及載運的 利潤 c[k]，但是貨櫃的總容量是 90，可能無法將貨物全部裝入，希望選出其中的若干項，其體積總和 不超過90，使得 利潤最大。（每一項貨物的體積為 1~100 的整數，而利潤是 1~60000 的整數。）

輸入格式

 第一行是貨品數量，接下來每行 各有兩筆數據，第一筆代表各項貨物的 體積，第二筆代表各項貨物的 利潤。

輸出格式

輸出每個 case 的最大 利潤。

Samples

4
60 70
30 60
20 50
35 40
10
8 16
80 88
33 66
13 26
77 150
95 195
45 90
20 41
40 13
68 20

case 1: 150
case 2: 176

原始資料

• Zero1 題號：a313
• Hydro 題號：Z0313
• Locale：zh_TW
• Display：practice