题目内容

小华这一年干得很出色，在部门里被当成标杆员工，领导打算给他发奖。

他能在礼品清单中挑四件，四件价钱加起来不得超过 $10000$ 元。

每件礼品带有互不相同的编号，以及可能相同的售价。

他希望四件总价尽量贴近上限；总价相同时，把编号从小到大排好，取字典序更小的那一套。

输入描述

第一行给出一个整数 $m$，表示清单里的礼品件数。

随后 $m$ 行，每行两个整数 $b_i$、$w_i$，依次是该件礼品的编号和售价。

凑不出符合要求的四件时，输出 $0$。

数据范围：

• $1 \le m \le 2000$
• $1 \le b_i, w_i \le 10000$

输出描述

若存在合法的四件礼品，输出四个编号，编号之间用空格隔开，并按升序排列。凑不齐则输出 $0$。

样例1

输入

6
1 100
2 100
3 8000
4 1800
5 1800
6 1800

输出

1 2 3 4

说明

$[1,2,3,4]$、$[1,2,3,5]$、$[1,2,3,6]$ 三组总价都是 $10000$，都已顶到上限。编号升序后字典序最小的是 $1\ 2\ 3\ 4$。

样例2

输入

5
1 3000
2 3000
3 3000
4 3000
5 2000

输出

0

说明

任意四件的总价都超过 $10000$ 元，因此输出 $0$。