12149. Аромати

Відправити розв'язок
Бали: 100
Time limit: 2.0s
Memory limit: 500M
Authors:
admin, admin2
Problem type
Allowed languages
C++, Java, Pascal, Python

У нас є \(N\) чашок морозива.

Аромат і смак \(i\)-ї чашки дорівнює \(F_i\) ​ і \(S_i\) ​ відповідно (\(S_i\) ​ — парне число).

Ви виберете і з’їсте дві з \(N\) чашок.

Ваше задоволення тут визначається наступним чином.

  • Нехай \(s\) і \(t\) ( \(s≥t\)) – смак спожитих чашок морозива.

    • Якщо дві чашки мають різні аромати, то ваше задоволення рівне \(s+t\);.

    • В іншому випадку ваше задоволення буде \(s + t/2\) ​.

Знайдіть максимально досяжне задоволення.

Обмеження

  • Усі вхідні значення є цілими числами.
  • \(2≤N≤3×10^5\)
  • \(1≤F_i ≤N\)
  • \(2≤S_i ≤10^9\)
  • \(S_i\) ​ є парним.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Наступні  \(N\) рядків містять цілі числа \(F_i, S_i\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

4
1 4
2 10
2 8
3 6

Приклад вихідних даних

16

Подумайте про те, щоб з’їсти другу та четверту чашки.

  • Друга чашка має аромат 2 і смак 10.
  • Четверта чашка має аромат 3 і смак 6.
  • Оскільки вони мають різні смаки, ваше задоволення становить 10 + 6=16.

Таким чином, ви можете отримати задоволення 16. Ви не можете досягти задоволення більше 16.

Приклад вхідних даних

4
4 10
3 2
2 4
4 12

Приклад вихідних даних

17

Коментарі


  • 1
    KossYuriy_67  commented on Гру. 17, 2023, 11:23 після полудня ← редагувати 4

    А можна якось отримати дані з тесту №11?


  • 1
    KossYuriy_67  commented on Гру. 16, 2023, 1:23 після полудня ← відректований

    Помилка в умові: "Якщо 2 чашки мають різні АРОМАТИ, тоді задоволення буде s+t; Інакше задоволення дорівнює s+t/2."


    • 2
      admin2  commented on Гру. 16, 2023, 7:47 після полудня ← відректований

      Дякую, виправив.