Задача необходимая в решении на С++

Концерт

Максимум баллов
:
100
Имя входного файла
:
concert.in
Имя выходного файла
:
concert.out
Ограничение по времени
:
1 сек
Ограничение по памяти
:
256 Мб
Известная музыкальная группа RockGroup1 планирует дать концерт на следующей неделе.
Они приготовили N песен: song_1, song_2, ..., song_n. Каждая песня характеризуется двумя параметрами: r_i и m_i - её рейтингом и её магией соответственно.
В течение выступления группа может сыграть любое количество своих песен. Длина песен не так важна, поскольку RockGroup1 настолько популярна, что её можно слушать вечно. Группа может исполнять свои песни в произвольном порядке, но не может исполнять какую-либо песню более одного раза.
Публика любит песни с высоким рейтингом, но не любит, когда значения магии соседних песен сильно различаются. Поэтому итоговое удовлетворение публики от концерта будет высчитываться следующим образом:


если song_x - первая песня концерта, то итоговое удовлетворение увеличится на r_x.
если перед song_x была проиграна песня song_y, то итоговое удовлетворение увеличится на r_x - (m_x - m_y)2.


Помогите группе оценить наибольшее возможное значение удовлетворения публики.

Формат файла входных данных:
Первая строка входных данных содержит одно целое число N - число приготовленных песен (1 <= N <= 3000).
Следующие N строк содержат описания каждой из песен. Cтрока с номером i + 1 содержит описание песни с номером i, где r_i ее рейтинг r_i и m_i её магия. (0 <= r_i, m_i <= 10000)

Формат файла выходных данных:
Единственная строка выходных данных должна содержать одно целое число - наибольшее возможное значение удовлетворения публики.

Пример:
concert.in
5
9 1
1 17
8 5
5 17
10 15

concert.out
12



Вот такой код я смог написать на Python

0