Задача
«Ну не гномы, а наказание какое-то!», – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь – другой уже проснулся! И так всю ночь.
У Белоснежки n гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать i-го гнома нужно ai минут, и после этого он будет спать ровно bi минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.
Например, пусть есть всего два гнома, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.
Входные данные
Первая строка входного файла содержит число n (1 <= n <= 10000), вторая строка содержит числа a1,a2,… an, третья – числа b1,b2,… bn (1 <= ai, bi <= 100000).
Выходные данные
Выведите в выходной файл n чисел – порядок, в котором нужно укладывать гномов спать. Если Белоснежке отдохнуть не удастся, выведите число -1.
Ввод |
Вывод |
2
1 10
10 20
|
2 1 |
(с) Григорьев Е., 2018