Задача №1782. Белоснежка и n гномов
«Ну не гномы, а наказание какое-то!», – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь – другой уже проснулся! И так всю ночь.
У Белоснежки \(n\) гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать \(i\)-го гнома нужно \(a_i\) минут, и после этого он будет спать ровно \(b_i\) минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.
Например, пусть есть всего два гнома, \(a_1\) = 1, \(b_1\) = 10, \(a_2\) = 10, \(b_2\) = 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.
Первая строка входного файла содержит число \(n\) (1 ≤ \(n\) ≤ \(10^5\)), вторая строка содержит числа \(a_1\),\(a_2\),… \(a_n\), третья – числа \(b_1\),\(b_2\),… \(b_n\) (1 ≤ \(a_i\), \(b_i\) ≤ \(10^9\)).
Выведите в выходной файл \(n\) чисел – порядок, в котором нужно укладывать гномов спать. Если Белоснежке отдохнуть не удастся, выведите число -1.
2 1 10 10 20
2 1
2 10 10 10 10
-1