e-olymp
Задачі

Белоснежка и n гномов

Белоснежка и n гномов

"_Ну не гномы, а наказание какое-то!_", – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь - другой уже проснулся! И так всю ночь.

У Белоснежки n гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать i-го гнома нужно ai минут, и после этого он будет спать ровно bi минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.

Например, пусть есть всего два гнома, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.

Входные данные

Первая строка содержит число n (1n105), вторая строка содержит числа a1, a2, ..., an, третья - числа b1, b2, ..., bn (1ai, bi109).

Выходные данные

Выведите n чисел - порядок, в котором нужно укладывать гномов спать. Если Белоснежке отдохнуть не удастся, выведите число -1.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
2
1 10
10 20
Вихідні дані #1
2 1
Вхідні дані #2
2
10 10
10 10
Вихідні дані #2
-1
Джерело 2006, XIV Командный чемпионат школьников Санкт-Петербурга по программированию, 6 ноября, Задача C