美味しさが最大のカップを一つ選び、\(X\) とします。\(X\) を食べることにして損はありません。（\(X\) 以外の \(2\) カップを食べようとしているなら、満足度を下げることなく片方を \(X\) と交換することができます。具体的には、\(2\) カップのうち片方だけが \(X\) と同じ味のカップならそれと \(X\) を交換すればよく、そうでなければどちらと交換しても構いません。）よって、食べるもう一つのカップとして残りの \(N - 1\) カップをすべて試すことで線形時間で問題を解けます。

実装例 (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)