まず、\(2\) 回以上買う商品はクーポンを貰うために買うものとして良いため、\(2\) 回以上買う商品は \(A_i\) が最小の商品のみとして良いです。

クーポンを使って購入する商品の個数を \(k\) とします。\(N-k < k\) である場合 \(2k-N\) 枚クーポンが不足するため、新たに \(2k-N\) 枚クーポンを購入する必要があります。

クーポンを使って購入する \(k\) 個の商品は \(A_i-B_i\) が大きい \(k\) 個として良いです。

これを各 \(k\) に対して計算し、それらの最小値を計算すると良いです。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

import sys

input = sys.stdin.readline
for _ in range(int(input())):
    N = int(input())
    base = 0
    minA = 10**9
    diff = []
    for _ in range(N):
        A, B = map(int, input().split())
        base += A
        minA = min(minA, A)
        diff.append(B - A)
    diff.sort()
    ans = base
    cur = base
    for k in range(1, N + 1):
        cur += diff[k - 1]
        ans = min(ans, cur + max(0, 2 * k - N) * minA)
    print(ans)