P5414. 奖励清单：最优四件礼品组合

场次：2026年9月9日-非AI方向 · 来源：CodeFun2000 P5414

题目描述

小华因为过去一年的突出表现，被部门树为标杆员工，主管决定允许他在一份礼品清单中挑选恰好四件作为奖励。清单中的每一件礼品都有唯一的编号和一个售价，不同礼品的售价可能相同。小华选出的四件礼品，其售价之和不能超过 10000 元。

他在选择时首先考虑让四件礼品的总售价尽可能接近 10000 元，有多种选法的时候他会选择排序后字典序最小的编号序列。

约束条件

• 清单中的礼品件数 $m$ 至少为 1，最多为 2000。
• 每件礼品的编号 $b_i$ 和售价 $w_i$ 均为不超过 10000 的正整数。

输入格式

第一行包含一个整数 $m$，表示礼品清单中的礼品件数。 接下来 $m$ 行，每行包含两个以空格分隔的整数 $b_i$ 和 $w_i$，分别表示某件礼品的编号和售价。

输出格式

如果不存在合法的四件礼品组合，输出 0。 否则，输出四个整数，表示所选四件礼品的编号；这些编号必须按升序排列，并用单个空格分隔。

示例

示例 1

输入：

3
1 100
2 200
3 300

输出：

0

说明：

清单中只有 3 件礼品，少于需要的 4 件。

因此不存在任何合法的四件组合，输出 0。

示例 2

输入：

4
10 1000
20 2000
30 3000
40 4000

输出：

10 20 30 40

说明：

清单中恰有 4 件礼品，因此只能将这四件全部选出。

总售价为 $1000+2000+3000+4000=10000$，没有超过预算 10000，所以编号升序输出为 10 20 30 40。

示例 3

输入：

5
1 2000
2 2000
3 2000
4 2000
5 2000

输出：

1 2 3 4

说明：

清单中共有 5 件礼品，任意选取 4 件时，由于每件售价均为 2000，总售价都是 $2000+2000+2000+2000=8000$。

这个总售价不超过预算 10000。所有组合的总售价相同，因此比较编号升序后的字典序；排除编号 5 后的 [1,2,3,4] 字典序最小，所以输出 1 2 3 4。

示例 4

输入：

6
1 3000
2 3000
3 3000
4 3000
5 1000
6 1000

输出：

1 2 3 5

说明：

四件售价均为 3000 的礼品总价为 $3000+3000+3000+3000=12000$，超过预算 10000，不合法。

可行的最高总价来自三件售价 3000 的礼品加一件售价 1000 的礼品[1,2,3,5]，总价为 $3000+3000+3000+1000=10000$。