題目描述

有一天，小紀來到 Kinda 餐廳吃飯。

這裏有 𝑁 種美食，每種美食均有各自的價格 𝑎_i 元，每吃一次能使小紀的滿足度提升 𝑏_i 。但是由於小紀討厭過於昂貴的物品，當一款美食大於一個定值 𝐾 的時候，他的滿足度只會提升 ⌊b_i / 2⌋。且每種美食都只能被選一次。

小紀目前帶了 𝑀 元，他希望找出一個方案，使得他所選的這些食物的價格和不超過 𝑀，而令到自己的滿足度最高。現在你是他的秘書，他要求你幫他算出他可能達到的滿足度的最大值。

輸入格式

第一行三個正整數 𝑁, 𝑀, 𝐾，以空格分隔。

接下來 𝑁 行，每行兩個正整數 𝑎_i , 𝑏_i ，以空格分隔。

輸出格式

小紀可能達到的滿足度的最大值。

Samples

["3 100 80 \r\n70 2 \r\n20 3 \r\n99 7","10 800 100 \r\n50 8 \r\n85 12 \r\n66 9 \r\n5 1 \r\n99 22 \r\n150 100 \r\n130 15 \r\n599 1000 \r\n288 125 \r\n1 7"]

["5","565"]

提示

數據範圍

[5 分, 1.0𝑠] 測試數據 1~10: 𝑁, 𝑀 ≤ 20, 𝑎_i , 𝑏_i ,𝐾 ≤ 100。

[10 分, 1.0𝑠] 測試數據 11~20: 𝑁, 𝑀 ≤ 10³, 𝑎_i , 𝑏_i ,𝐾 ≤ 10⁴ 。

原始資料

• Zero1 題號：b290
• Hydro 題號：Z1290
• Locale：zh_TW
• Display：practice