{"problem":{"name":"不等价交换法则","description":{"content":"你有 $n$ **件**商品可以买，其中第 $i$ 件的价格为 $a_i$。 蓝会给出一个正整数 $w$，代表你有 $w$ 元钱。你仅可以选择**一件**商品购买。店主允许你用已有的商品交换剩余的商品（当然了，也可以不换），但你交换获得的商品的价值和必须小于等于你用于交换的商品价值和。你想要知道，你最多能获得多少件商品。 注意：不能用空集交换其他商品。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8444"},"statements":[{"statement_type":"Markdown","content":"你有 $n$ **件**商品可以买，其中第 $i$ 件的价格为 $a_i$。\n\n蓝会给出一个正整数 $w$，代表你有 $w$ 元钱。你仅可以选择**一件**商品购买。店主允许你用已有的商品交换剩余的商品（当然了，也可以不换），但你交换获得的商品的价值和必须小于等于你用于交换的商品价值和。你想要知道，你最多能获得多少件商品。\n\n注意：不能用空集交换其他商品。\n\n## Input\n\n第一行一个正整数 $n$，表示商品个数。\n\n接下来一行 $n$ 个正整数，表示 $\\{a_n\\}$。\n\n接下来一行 $1$ 个正整数，表示 $w$。\n\n## Output\n\n一个正整数，表示询问的结果。 \n\n[samples]\n\n## Background\n\n天弓千亦，市场之神，拥有着剥夺所有权的能力。\n\n她希望着重建市场，在严格而公正的交易中一点点恢复自己的神力。但她看向世间一处处交易之所时，无力感却又遮住了她心中虹色的月光，把她的不甘一点点化作现实的泪。\n\n她一次次在梦中经历着那个晚上。孤独的、神力尽失的她，紧紧攥住她那空白的卡牌，却被灵梦一把夺走。最后一张希望，也伴着虹色的月，消逝在永远的幻想中了。\n\n也许交易本身就是不等价的吧，她想。\n\n## Note\n\n【样例解释】\n\n买价值为 $2$ 的物品，并交换为两个价值为 $1$ 的物品。\n\n【数据范围及约束】\n\n对于 $40\\%$ 的数据，$n\\leq 10$。\n\n对于 $100\\%$ 的数据，$1 \\leq n\\leq10^6$，$0 \\leq a_i\\leq 10^9$，$1 \\leq w\\leq2\\times10^{9}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8444","tags":["贪心","洛谷原创","洛谷月赛"],"sample_group":[["3 \n1 1 2\n5","2"]],"created_at":"2026-03-03 11:09:25"}}