English · Original
Chinese · Translation
Formal · Original
Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take _t__i_ seconds to save _i_\-th item. In addition, for each item, he estimated the value of _d__i_ — the moment after which the item _i_ will be completely burned and will no longer be valuable for him at all. In particular, if _t__i_ ≥ _d__i_, then _i_\-th item cannot be saved.
Given the values _p__i_ for each of the items, find a set of items that Polycarp can save such that the total value of this items is maximum possible. Polycarp saves the items one after another. For example, if he takes item _a_ first, and then item _b_, then the item _a_ will be saved in _t__a_ seconds, and the item _b_ — in _t__a_ + _t__b_ seconds after fire started.
## Input
The first line contains a single integer _n_ (1 ≤ _n_ ≤ 100) — the number of items in Polycarp's house.
Each of the following _n_ lines contains three integers _t__i_, _d__i_, _p__i_ (1 ≤ _t__i_ ≤ 20, 1 ≤ _d__i_ ≤ 2 000, 1 ≤ _p__i_ ≤ 20) — the time needed to save the item _i_, the time after which the item _i_ will burn completely and the value of item _i_.
## Output
In the first line print the maximum possible total value of the set of saved items. In the second line print one integer _m_ — the number of items in the desired set. In the third line print _m_ distinct integers — numbers of the saved items _in the order Polycarp saves them_. Items are 1-indexed in the same order in which they appear in the input. If there are several answers, print any of them.
[samples]
## Note
In the first example Polycarp will have time to save any two items, but in order to maximize the total value of the saved items, he must save the second and the third item. For example, he can firstly save the third item in 3 seconds, and then save the second item in another 2 seconds. Thus, the total value of the saved items will be 6 + 5 = 11.
In the second example Polycarp can save only the first item, since even if he immediately starts saving the second item, he can save it in 3 seconds, but this item will already be completely burned by this time.
Polycarp 遇到了严重的麻烦——他的房子着火了！现在是时候抢救最珍贵的物品了。Polycarp 估计抢救第 #cf_span[i] 个物品需要 #cf_span[ti] 秒。此外，对于每个物品，他估计了值 #cf_span[di]——即该物品 #cf_span[i] 将完全烧毁、不再具有价值的时刻。特别地，如果 #cf_span[ti ≥ di]，则第 #cf_span[i] 个物品无法被抢救。
给定每个物品的值 #cf_span[pi]，请找出一个 Polycarp 可以抢救的物品集合，使得这些物品的总价值最大。Polycarp 一个接一个地抢救物品。例如，如果他先抢救物品 #cf_span[a]，再抢救物品 #cf_span[b]，那么物品 #cf_span[a] 将在 #cf_span[ta] 秒后被抢救，物品 #cf_span[b] 将在 #cf_span[ta + tb] 秒后被抢救（从火灾开始计时）。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— Polycarp 房屋中物品的数量。
接下来的 #cf_span[n] 行，每行包含三个整数 #cf_span[ti, di, pi] (#cf_span[1 ≤ ti ≤ 20], #cf_span[1 ≤ di ≤ 2 000], #cf_span[1 ≤ pi ≤ 20]) —— 抢救第 #cf_span[i] 个物品所需的时间、该物品完全烧毁的时间、以及该物品的价值。
第一行输出可抢救物品集合的最大可能总价值。第二行输出一个整数 #cf_span[m] —— 所选集合中物品的数量。第三行输出 #cf_span[m] 个互不相同的整数 —— 按 Polycarp 抢救顺序排列的被抢救物品的编号。物品编号从 1 开始，与输入中的顺序一致。如果有多个答案，输出任意一个即可。
在第一个例子中，Polycarp 有足够时间抢救任意两个物品，但为了最大化抢救物品的总价值，他必须抢救第二个和第三个物品。例如，他可以先抢救第三个物品，耗时 #cf_span[3] 秒，然后抢救第二个物品，再耗时 #cf_span[2] 秒。因此，被抢救物品的总价值为 #cf_span[6 + 5 = 11]。
在第二个例子中，Polycarp 只能抢救第一个物品，因为即使他立即开始抢救第二个物品，也需要 #cf_span[3] 秒才能完成，但此时该物品已经完全烧毁。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— Polycarp 房屋中物品的数量。接下来的 #cf_span[n] 行，每行包含三个整数 #cf_span[ti, di, pi] (#cf_span[1 ≤ ti ≤ 20], #cf_span[1 ≤ di ≤ 2 000], #cf_span[1 ≤ pi ≤ 20]) —— 抢救第 #cf_span[i] 个物品所需的时间、该物品完全烧毁的时间、以及该物品的价值。
## Output
第一行输出可抢救物品集合的最大可能总价值。第二行输出一个整数 #cf_span[m] —— 所选集合中物品的数量。第三行输出 #cf_span[m] 个互不相同的整数 —— 按 Polycarp 抢救顺序排列的被抢救物品的编号。物品编号从 1 开始，与输入中的顺序一致。如果有多个答案，输出任意一个即可。
[samples]
## Note
在第一个例子中，Polycarp 有足够时间抢救任意两个物品，但为了最大化抢救物品的总价值，他必须抢救第二个和第三个物品。例如，他可以先抢救第三个物品，耗时 #cf_span[3] 秒，然后抢救第二个物品，再耗时 #cf_span[2] 秒。因此，被抢救物品的总价值为 #cf_span[6 + 5 = 11]。在第二个例子中，Polycarp 只能抢救第一个物品，因为即使他立即开始抢救第二个物品，也需要 #cf_span[3] 秒才能完成，但此时该物品已经完全烧毁。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of items.
For each item $ i \in \{1, \dots, n\} $, define:
- $ t_i \in \mathbb{Z}^+ $: time required to save item $ i $,
- $ d_i \in \mathbb{Z}^+ $: deadline by which item $ i $ must be saved (burns at time $ d_i $),
- $ p_i \in \mathbb{Z}^+ $: value of item $ i $.
Let $ S \subseteq \{1, \dots, n\} $ be a subset of items to be saved, and let $ \sigma: \{1, \dots, |S|\} \to S $ be an ordering (permutation) of $ S $, representing the sequence in which items are saved.
**Constraints**
1. $ 1 \leq n \leq 100 $
2. For each $ i \in \{1, \dots, n\} $:
- $ 1 \leq t_i \leq 20 $
- $ 1 \leq d_i \leq 2000 $
- $ 1 \leq p_i \leq 20 $
3. For a valid sequence $ \sigma $, the cumulative saving time up to item $ \sigma(j) $ must satisfy:
$$
\sum_{k=1}^{j} t_{\sigma(k)} < d_{\sigma(j)} \quad \forall j \in \{1, \dots, |S|\}
$$
(Note: strict inequality because the item burns *at* $ d_i $, so must be saved *before*.)
**Objective**
Maximize the total value:
$$
\max_{S, \sigma} \sum_{i \in S} p_i
$$
subject to the above temporal constraints.
Additionally, output:
- The maximum total value,
- The size $ m = |S| $,
- The sequence $ \sigma(1), \sigma(2), \dots, \sigma(m) $ (1-indexed item indices).
API Response (JSON)
{
"problem": {
"name": "E. Fire",
"description": {
"content": "Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take _t__i_ seconds to save _i_\\-th item. In addition, for eac",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF864E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take _t__i_ seconds to save _i_\\-th item. In addition, for eac...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Polycarp 遇到了严重的麻烦——他的房子着火了！现在是时候抢救最珍贵的物品了。Polycarp 估计抢救第 #cf_span[i] 个物品需要 #cf_span[ti] 秒。此外，对于每个物品，他估计了值 #cf_span[di]——即该物品 #cf_span[i] 将完全烧毁、不再具有价值的时刻。特别地，如果 #cf_span[ti ≥ di]，则第 #cf_span[i] 个物品无法被抢...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of items. \nFor each item $ i \\in \\{1, \\dots, n\\} $, define: \n- $ t_i \\in \\mathbb{Z}^+ $: time required to save item $ i $, \n- $ d_i \\in \\m...",
"is_translate": false,
"language": "Formal"
}
]
}