English · Original
Chinese · Translation
Formal · Original
Nick has _n_ bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda _a__i_ and bottle volume _b__i_ (_a__i_ ≤ _b__i_).
Nick has decided to pour all remaining soda into minimal number of bottles, moreover he has to do it as soon as possible. Nick spends _x_ seconds to pour _x_ units of soda from one bottle to another.
Nick asks you to help him to determine _k_ — the minimal number of bottles to store all remaining soda and _t_ — the minimal time to pour soda into _k_ bottles. A bottle can't store more soda than its volume. All remaining soda should be saved.
## Input
The first line contains positive integer _n_ (1 ≤ _n_ ≤ 100) — the number of bottles.
The second line contains _n_ positive integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 100), where _a__i_ is the amount of soda remaining in the _i_\-th bottle.
The third line contains _n_ positive integers _b_1, _b_2, ..., _b__n_ (1 ≤ _b__i_ ≤ 100), where _b__i_ is the volume of the _i_\-th bottle.
It is guaranteed that _a__i_ ≤ _b__i_ for any _i_.
## Output
The only line should contain two integers _k_ and _t_, where _k_ is the minimal number of bottles that can store all the soda and _t_ is the minimal time to pour the soda into _k_ bottles.
[samples]
## Note
In the first example Nick can pour soda from the first bottle to the second bottle. It will take 3 seconds. After it the second bottle will contain 3 + 3 = 6 units of soda. Then he can pour soda from the fourth bottle to the second bottle and to the third bottle: one unit to the second and two units to the third. It will take 1 + 2 = 3 seconds. So, all the soda will be in two bottles and he will spend 3 + 3 = 6 seconds to do it.
Nick 在生日后还剩下 #cf_span[n] 瓶苏打水。每瓶苏打水由两个值描述：剩余的苏打水量 #cf_span[ai] 和瓶子的容积 #cf_span[bi]（#cf_span[ai ≤ bi]）。
Nick 决定将所有剩余的苏打水倒入最少数量的瓶子中，并且他希望尽快完成。Nick 花费 #cf_span[x] 秒将 #cf_span[x] 单位的苏打水从一个瓶子倒入另一个瓶子。
Nick 请你帮他确定 #cf_span[k] —— 存储所有剩余苏打水所需的最少瓶子数，以及 #cf_span[t] —— 将苏打水倒入 #cf_span[k] 个瓶子所需的最少时间。每个瓶子的容量不能超过其容积。所有剩余的苏打水都必须被保存下来。
第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）—— 瓶子的数量。
第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 100]），其中 #cf_span[ai] 表示第 #cf_span[i] 瓶中剩余的苏打水量。
第三行包含 #cf_span[n] 个正整数 #cf_span[b1, b2, ..., bn]（#cf_span[1 ≤ bi ≤ 100]），其中 #cf_span[bi] 表示第 #cf_span[i] 瓶的容积。
保证对于任意 #cf_span[i]，都有 #cf_span[ai ≤ bi]。
仅输出一行，包含两个整数 #cf_span[k] 和 #cf_span[t]，其中 #cf_span[k] 是能存储所有苏打水的最少瓶子数，#cf_span[t] 是将苏打水倒入 #cf_span[k] 个瓶子所需的最少时间。
在第一个例子中，Nick 可以将第一个瓶子中的苏打水倒入第二个瓶子。这需要 3 秒。之后，第二个瓶子将含有 #cf_span[3 + 3 = 6] 单位的苏打水。然后他可以将第四个瓶子中的苏打水倒入第二个和第三个瓶子：1 单位倒入第二个，2 单位倒入第三个。这需要 #cf_span[1 + 2 = 3] 秒。因此，所有苏打水将被存入两个瓶子中，总共花费 #cf_span[3 + 3 = 6] 秒。
## Input
第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）—— 瓶子的数量。第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 100]），其中 #cf_span[ai] 表示第 #cf_span[i] 瓶中剩余的苏打水量。第三行包含 #cf_span[n] 个正整数 #cf_span[b1, b2, ..., bn]（#cf_span[1 ≤ bi ≤ 100]），其中 #cf_span[bi] 表示第 #cf_span[i] 瓶的容积。保证对于任意 #cf_span[i]，都有 #cf_span[ai ≤ bi]。
## Output
仅输出一行，包含两个整数 #cf_span[k] 和 #cf_span[t]，其中 #cf_span[k] 是能存储所有苏打水的最少瓶子数，#cf_span[t] 是将苏打水倒入 #cf_span[k] 个瓶子所需的最少时间。
[samples]
## Note
在第一个例子中，Nick 可以将第一个瓶子中的苏打水倒入第二个瓶子。这需要 3 秒。之后，第二个瓶子将含有 #cf_span[3 + 3 = 6] 单位的苏打水。然后他可以将第四个瓶子中的苏打水倒入第二个和第三个瓶子：1 单位倒入第二个，2 单位倒入第三个。这需要 #cf_span[1 + 2 = 3] 秒。因此，所有苏打水将被存入两个瓶子中，总共花费 #cf_span[3 + 3 = 6] 秒。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of bottles.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the remaining soda amounts, with $ 1 \le a_i \le 100 $.
Let $ B = (b_1, b_2, \dots, b_n) \in \mathbb{Z}^n $ be the bottle volumes, with $ 1 \le b_i \le 100 $ and $ a_i \le b_i $ for all $ i $.
Let $ S = \sum_{i=1}^n a_i $ be the total soda volume.
**Constraints**
1. $ 1 \le n \le 100 $
2. $ 1 \le a_i \le b_i \le 100 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Find the minimal number of bottles $ k \in \mathbb{Z}^+ $ and minimal pouring time $ t \in \mathbb{Z}_{\ge 0} $ such that:
- All $ S $ units of soda are stored in exactly $ k $ bottles,
- No bottle $ i $ contains more than $ b_i $ units,
- $ k $ is minimized: $ k = \min \left\{ m \in \mathbb{Z}^+ \,\middle|\, \exists \, I \subseteq \{1,\dots,n\}, |I| = m, \sum_{i \in I} b_i \ge S \right\} $,
- $ t $ is minimized: $ t = \sum_{i \notin I} a_i $, where $ I $ is a set of $ k $ bottles with total capacity $ \ge S $, and soda is poured *only* from bottles not in $ I $ into bottles in $ I $, optimally assigned to minimize total poured volume.
**Note**: The minimal time $ t $ equals the total soda removed from the $ n - k $ bottles that are emptied — which is $ S - \text{(maximal soda already in the chosen } k \text{ bottles)} $. To minimize $ t $, maximize the soda retained in the $ k $ selected bottles, subject to their capacities. Thus, select the $ k $ bottles with largest capacities and greedily retain as much of their original soda as possible (up to their volume), then the rest must be poured in.
API Response (JSON)
{
"problem": {
"name": "J. Bottles",
"description": {
"content": "Nick has _n_ bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda _a__i_ and bottle volume _b__i_ (_a__i_ ≤ _b__i_). Nick has decided to pour all ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF730J"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Nick has _n_ bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda _a__i_ and bottle volume _b__i_ (_a__i_ ≤ _b__i_).\n\nNick has decided to pour all ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Nick 在生日后还剩下 #cf_span[n] 瓶苏打水。每瓶苏打水由两个值描述：剩余的苏打水量 #cf_span[ai] 和瓶子的容积 #cf_span[bi]（#cf_span[ai ≤ bi]）。\n\nNick 决定将所有剩余的苏打水倒入最少数量的瓶子中，并且他希望尽快完成。Nick 花费 #cf_span[x] 秒将 #cf_span[x] 单位的苏打水从一个瓶子倒入另一个瓶子。\n\nNic...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of bottles. \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the remaining soda amounts, with $ 1 \\le a_i \\le 100 $. \nLet $ B = (b_1...",
"is_translate": false,
"language": "Formal"
}
]
}