First, we may assume that any item bought twice or more is bought to get a coupon, so such an item will always have the minimum \(A_i\).

Let \(k\) be the number of items purchased with a coupon. If \(N-k < k\), we are short of \((2k - N)\) coupons, so \((2k-N)\) new coupons must be purchased.

We may assume that the \(k\) items purchased with a coupon are the \(k\) items with the largest \(A_i - B_i\).

Calculate this for all \(k\), and find the minimum value among them.

The problem can be solved by properly implementing this.

Sample code (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)