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

Ну не гномы, а наказание какое-то! Подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь, другой уже проснулся! И так всю ночь. У Белоснежки n гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать i-го гнома нужно a_i минут, и после этого он будет спать ровно b_i минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.

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

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

Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 10⁵), вторая строка содержит числа a₁, a₂, . . . a_n, третья - числа b₁, b₂, . . . b_n (1 ≤ a_i, b_i ≤ 10⁹).

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

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

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]