{"problem":{"name":"[GESP202309 六级] 小杨买饮料","description":{"content":"小杨来到了一家商店，打算购买一些饮料。这家商店总共出售 $N$ 种饮料，编号从 $0$ 至 $N-1$，其中编号为 $i$ 的饮料售价 $c_i$ 元，容量 $l_i$ 毫升。 小杨的需求有如下几点： 1. 小杨想要尽可能尝试不同种类的饮料，因此他希望每种饮料至多购买 $1$ 瓶； 2. 小杨很渴，所以他想要购买总容量不低于 $L$ 的饮料； 3. 小杨勤俭节约，所以在 $1$ 和 $2$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3873"},"statements":[{"statement_type":"Markdown","content":"小杨来到了一家商店，打算购买一些饮料。这家商店总共出售 $N$ 种饮料，编号从 $0$ 至 $N-1$，其中编号为 $i$ 的饮料售价 $c_i$ 元，容量 $l_i$ 毫升。\n\n小杨的需求有如下几点：\n\n1. 小杨想要尽可能尝试不同种类的饮料，因此他希望每种饮料至多购买 $1$ 瓶；\n\n2. 小杨很渴，所以他想要购买总容量不低于 $L$ 的饮料；\n\n3. 小杨勤俭节约，所以在 $1$ 和 $2$ 的前提下，他希望使用尽可能少的费用。\n\n方便起见，你只需要输出最少花费的费用即可。特别地，如果不能满足小杨的要求，则输出 `no solution`。\n\n## Input\n\n第一行两个整数 $N,L$。\n\n接下来 $N$行，依次描述第 $i=0,1,\\cdots,N-1$ 种饮料：每行两个整数 $c_i,l_i$。\n\n## Output\n\n输出一行一个整数，表示最少需要花费多少钱，才能满足小杨的要求。特别地，如果不能满足要求，则输出 `no solution`。\n\n[samples]\n\n## Background\n\n对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1132>\n\n## Note\n\n**样例 1 解释**\n\n小杨可以购买 $2,3,5$ 号饮料，总计获得 $50+40+20=110$ 毫升饮料，花费 $2+4+3=9$ 元。\n\n如果只考虑前两项需求，小杨也可以购买 $2,4,5$ 号饮料，它们的容量总和为 $50+30+20=100$ 毫升，恰好可以满足需求。但遗憾的是，这个方案需要花费 $2+5+3=10$ 元。\n\n**样例 2 解释**\n\n$1,2,3,4$ 号饮料总计 $140$ 毫升，如每种饮料至多购买 $1$ 瓶，则恰好无法满足需求，因此只能花费 $100$ 元购买 $0$ 号饮料。\n\n**数据规模**\n\n对于 $40\\%$ 的测试点，保证 $N \\le 20;1\\le L \\le 100; l_i \\le 100$。\n\n对于 $70\\%$ 的测试点，保证 $l_i \\le 100$。\n\n对于 $100\\%$ 的测试点，保证 $1\\le N \\le 500;1\\le L \\le 2000; 1\\le c_i,l_i \\le 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3873","tags":["动态规划 DP","2023","背包 DP","GESP"],"sample_group":[["5 100\n100 2000\n2 50\n4 40\n5 30\n3 20","9"],["5 141\n100 2000\n2 50\n4 40\n5 30\n3 20","100"],["4 141\n2 50\n4 40\n5 30\n3 20","no solution"]],"created_at":"2026-03-03 11:09:25"}}