Задачи и сроки
Предположим, у вас есть
n задач, для каждой из которых задан дедлайн и прибыль, которая выплачивается, если вы успеваете выполнить задачу до окончания дедлайна. Нужно определить, какую максимальную суммарную прибыль можно получить. На выполнение каждой задачи уходит 1 день. Если задача не закончена к моменту дедлайна, прибыль за неё не начисляется.Вы начинаете работу с 1-го дня. Сколько всего вы можете заработать?
Входные данные
В первой строке входных данных содержится одно целое число
n (1 ≤ n ≤ ) — общее количество задач.В следующих
n строках записаны пары целых чисел (1 ≤ , ≤ ), где — дедлайн задачи, а — прибыль за её своевременное выполнение.Выходные данные
Программа должна вывести максимально возможную суммарную прибыль.
Примеры
Входные данные | Выходные данные |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
Пояснение
- 10 + 3 + 7
- Сначала выполняем задачу с дедлайном 1 ⇒ получаем 3
- Затем выполняем задачу с дедлайном 2 ⇒ получаем 7
- Наконец выполняем задачу с дедлайном 4 ⇒ получаем 10
- 100 + 200 + 300 + 200 (выполняем только задачи с дедлайном 4)
- Сначала выполняем задачу с прибылью 100
- Затем задачу с прибылью 200
- После этого задачу с прибылью 300
- И в конце задачу с прибылью 200
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB