Фредди работает курьером у Вито Маретти. Однажды утром он получил задание
доставить N контейнеров с виски — все в разные города штата.
На доставку каждого контейнера из списка уйдет по одному дню. Но у каждого
из заказов (один заказ — один контейнер) есть свой срок доставки и
свое вознаграждение для Фредди. За просроченный заказ Фредди не получит
нисколько денег, а может и нарваться на неприятности, так что доставлять
такие контейнеры нет никакого смысла. Помогите ему составить график
работы, который принесет максимальную прибыль, — Фредди в долгу не
останется!
Исходные данные
Первая строка содержит число N, количество заказов (1 ≤ N ≤ 1000). В каждой из последующих N строк находится по два целых числа: срок доставки контейнера и размер вознаграждения. Срок доставки — от 1 до 100000 дней, премия — от 1 до 100000 долларов.
Результат
В первой строке должно быть количество контейнеров, которые доставит
Фредди. Вторая строка должна содержать номера этих контейнеров через
пробел в том порядке, в каком их нужно доставлять. Доставка просроченных
заказов недопустима. Если решений несколько, выведите любое.
Пример
исходные данные | результат |
---|
4
1 17
5 15
2 10
2 11
| 3
1 4 2
|
Автор задачи: Никита Рыбак
Источник задачи: XII командный чемпионат школьников Свердловской области по программированию (15 октября 2005 года)