思路：贪心

分别计算每个任务的总能源开销，第$i$个任务的总能源开销为$e_i \times (n - i + 1)$

然后对任务按照总能源开销从小到大进行排序，优先启动总能源开销小的任务

时间复杂度

$O(nlogn)$

题目内容

在一个持续 n 天的项目周期内，有 n 个可选自动化任务，编号为 1 到 n。第 i 个任务若被启动，会从第 i 天开始持续运行到第 n 天，并且每天消耗 $e_i$ 单位能源。项目总可用能源为 m 单位。

第 i 个任务的总能源开销为 $e_i \times (n - i + 1)$。多个任务同时运行时，每天的总消耗等于当天运行任务的消耗之和。你希望选择若干个任务启动，使得总能源开销不超过 m，且启动的任务数量尽可能多。求最多可以启动的任务数量。

数据规模：$1 \le n \le 100$，$1 \le m \le 10^6$，$1 \le e_i \le 10^4$。

输入描述

第一行包含两个整数 n 和 m，分别表示任务数量和能源总预算，满足 $1 \le n \le 100$ 且 $1 \le m \le 10^6$。 第二行包含 n 个整数 $e_1, e_2, \ldots, e_n$，表示按任务编号给出的每日能源消耗，满足 $1 \le e_i \le 10^4$。

输出描述

输出一个整数，表示在总能源开销不超过 m 的前提下最多可以启动的任务数量。

样例1

输入

4 10
1 1 1 4

输出

3

说明

第 i 个任务的总开销为 $e_i \times (n - i + 1)$。

计算各任务总开销：

• 任务 1：$1 \times 4 = 4$
• 任务 2：$1 \times 3 = 3$
• 任务 3：$1 \times 2 = 2$
• 任务 4：$4 \times 1 = 4$

排序后总开销为 2, 3, 4, 4，预算为 10。前三个任务总开销 2 + 3 + 4 = 9 \le 10；再加入第四个任务后总开销为 13 > 10，超出预算。

因此最多可以启动 3 个任务。

样例2

输入

5 20
2 3 1 4 5

输出

3

说明

计算各任务总开销： 任务 1：$2 \times 5 = 10$ 任务 2：$3 \times 4 = 12$ 任务 3：$1 \times 3 = 3$ 任务 4：$4 \times 2 = 8$ 任务 5：$5 \times 1 = 5$

排序后为 3, 5, 8, 10, 12。预算为 20。 前一个任务和为 3 \le 20；前两个为 8 \le 20；前三个为 16 \le 20；前四个为 26 > 20。

因此最多启动 3 个任务。

样例3

输入

3 1
5 4 3

输出

0

说明

计算各任务总开销： 任务 1：$5 \times 3 = 15$ 任务 2：$4 \times 2 = 8$ 任务 3：$3 \times 1 = 3$

即使选择总开销最小的任务 3，也需要 3 单位能源，而预算只有 1 单位。 因为 3 > 1，无法启动任何任务。

因此最多启动 0 个任务。