Let \(X\) be a cup with the greatest deliciousness. There is no harm in choosing to eat \(X\). (If you are going to eat any two cups other than \(X\), you can replace one of them with \(X\) without reducing your satisfaction. Specifically, if only one of the two cups has the same flavor as \(X\), you can replace it with \(X\); otherwise, you can replace either.) Thus, you can solve the problem in linear time by trying each of the remaining \(N - 1\) cups as the other cup to eat.

Sample Implementation (Python)

N = int(input())
F, S = [], []
maxS, choice = 0, -1
for i in range(N):
    f, s = map(int, input().split())
    if s > maxS:
        maxS = s
        choice = i
    F.append(f)
    S.append(s)

ans = 0
for i in range(N):
    if i != choice:
        t = maxS + S[i] // (2 if F[i] == F[choice] else 1)
        ans = max(ans, t)
print(ans)