a132. TOI 2025/11 潛力組：餅乾促銷

題目描述

商店提供 N 種餅乾促銷方案。第 i 種方案花 Aᵢ 元，可以拿到 Aᵢ 包購買的餅乾及 Bᵢ 包贈品，共 Aᵢ+Bᵢ 包。每種方案都能重複使用，也可以混合使用；不能在方案以外單買餅乾。請計算至少取得 C 包餅乾所需的最少花費，允許拿到超過 C 包。

輸入格式

第一行有 N、C，接著 N 行各有 Aᵢ、Bᵢ。

• 1 ≤ N ≤ 100，1 ≤ C ≤ 10000
• 1 ≤ Bᵢ ≤ Aᵢ ≤ 1000

輸出格式

輸出最少需要支付的整數金額。

來源

TOI 2025 年 11 月潛力組〈餅乾促銷〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202511/Cookies.pdf