a130. TOI 2026/05 潛力組：自助餐

題目描述

餐廳有 N 類料理，第 i 類提供 Mᵢ 道不同料理。每道料理都有價格與美味值。你可以選擇任意料理，每道最多一份，也可以整類不買；每一類最多選 R 道，所有料理的總價格不得超過預算 P。

請求出可取得的最大美味值總和。注意 R 是每一類的上限，不是全部料理的總數上限。

輸入格式

第一行有 N、P、R。接著是 N 個區塊：每個區塊先輸入 Mᵢ，再輸入 Mᵢ 行，每行為一份料理的價格 Cᵢⱼ 與美味值 Dᵢⱼ。

• 1 ≤ N ≤ 100，1 ≤ P ≤ 2000，1 ≤ R ≤ 10
• Mᵢ ≥ 1，所有 Mᵢ 的總和不超過 1000
• 1 ≤ Cᵢⱼ ≤ min(100,P)，1 ≤ Dᵢⱼ ≤ 100

輸出格式

輸出預算與各類數量限制內，最大的美味值總和。

來源

TOI 2026 年 5 月潛力組〈自助餐〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202605/Buffet.pdf