ACAC 题库 ac.isam.top
GitHub
第 474 场 AtCoder Beginner Contest
E
一次性优惠券
One Time Coupon
AtCoder
⌀ 1153
原题
← DG →

一次性优惠券AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

A certain shop sells $N$ types of products. Each product can be purchased any number of times.

某商店出售 $N$ 种商品。每种商品都可以购买任意多次。AI (CI翻译)

The $i$-th type of product $(1\le i\le N)$ can be bought in the following two ways:

第 $i$ 种商品 $(1\le i\le N)$ 有以下两种购买方式：AI (CI翻译)

  • Buy it for $A_i$ yen without using a coupon, and receive one coupon.
  • Use one coupon and buy it for $B_i$ yen.
  • 不使用优惠券，花费 $A_i$ 日元购买，并获得一张优惠券。
  • 使用一张优惠券，花费 $B_i$ 日元购买。
AI (CI翻译)

Initially, you have no coupons.

初始时，你没有优惠券。AI (CI翻译)

Find the minimum amount of money required to buy every product at least once.

求至少购买每种商品一次所需的最少金额。AI (CI翻译)

You are given $T$ test cases; solve each of them.

给定 $T$ 组测试数据，请分别求解。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $1\le T\le 2\times 10^5$
  • $1\le N\le 2\times 10^5$
  • $1\le B_i < A_i \le 10^9$
  • The sum of $N$ over all test cases is at most $2\times 10^5$.
  • All input values are integers.
  • $1\le T\le 2\times 10^5$
  • $1\le N\le 2\times 10^5$
  • $1\le B_i < A_i \le 10^9$
  • 所有测试数据中 $N$ 的总和不超过 $2\times 10^5$。
  • 输入的所有数值均为整数。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
AI (CI翻译)

Each test case is given in the following format:

每组测试数据按以下格式给出：AI (CI翻译)

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answers for the test cases in order, separated by newlines.

按顺序输出各组测试数据的答案，每个答案占一行。AI (CI翻译)

样例

Input #1
3
5
11 6
6 5
2 1
8 3
7 4
4
5 1
5 2
5 3
5 4
6
24 13
24 2
50 12
35 25
28 26
10 1
Output #1
23
13
100
Consider the first test case. For example, by acting as follows, you can buy every product at least once for $23$ yen: - Buy the second type of product for $6$ yen without using a coupon. You now have $1$ coupon. - Buy the third type of product for $2$ yen without using a coupon. You now have $2$ coupons. - Buy the third type of product for $2$ yen without using a coupon. You now have $3$ coupons. - Use a coupon to buy the first type of product for $6$ yen. You now have $2$ coupons. - Use a coupon to buy the fourth type of product for $3$ yen. You now have $1$ coupon. - Use a coupon to buy the fifth type of product for $4$ yen. You now have $0$ coupons. It is impossible to buy every product at least once for less than $23$ yen, so output $23$ on the first line.
题目信息
题号
abc474_e
所属比赛
第 474 场 AtCoder Beginner Contest
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。