注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "festival.h"。

题目描述

节日上 Nayra 正在玩一个游戏，大奖是一次去红湖（Laguna Colorada）的旅行。游戏中玩家使用代币购买礼券。每购买一张礼券都有可能会获得额外的代币。游戏的目标是获得尽可能多的礼券。

开始时她有 $A$ 枚代币。游戏中一共有 $N$ 张礼券，从 $0$ 到 $N-1$ 编号。Nayra 需要支付 $P[i]$ 枚代币（$0 \leq i < N$）来购买礼券 $i$（购买前她至少要有 $P[i]$ 枚代币）。每张礼券最多只能购买一次。

此外，每张礼券 $i$（$0 \leq i < N$）都指定了类型，记为 $T[i]$，其值为 $1$ 到 $4$ 之间的整数。当 Nayra 购买礼券 $i$ 后，她剩余的代币数量将乘以 $T[i]$。形式化地，如果她在游戏的某个时刻有 $X$ 枚代币，并购买了礼券 $i$（要求 $X \geq P[i]$），那么购买后她将有 $(X - P[i]) \cdot T[i]$ 枚代币。

你的任务是确定 Nayra 应该购买哪些礼券以及按什么顺序来购买，使她最终拥有的礼券数量最大化。如果有多种购买序列能达成该目标，你可以回答其中任意一种。

实现细节

你要实现以下函数：

std::vector<int> max_coupons(int A, std::vector<int> P,
    std::vector<int> T)

• $A$: Narya 初始拥有的代币数量。
• $P$: 长度为 $N$ 的数组，表示礼券的价格。
• $T$: 长度为 $N$ 的数组，表示礼券的类型。
• 对每个测试用例，该函数恰好被调用一次。

该函数应返回一个数组 $R$，按以下规则表示 Narya 的购买计划：

• 数组 $R$ 的长度应等于她最多可以购买的礼券数量。
• 数组中的元素为她购买的礼券编号，按购买的顺序排列。也就是说，她首先购买礼券 $R[0]$，然后购买礼券 $R[1]$，以此类推。
• $R$ 中所有的元素互不相同。

如果无法购买任何礼券，则 $R$ 应为空数组。

约束条件

• $1 \leq N \leq 200\,000$
• $1 \leq A \leq 10^{9}$
• 对每个满足 $0 \leq i < N$ 的 $i$，都有 $1 \leq P[i] \leq 10^{9}$。
• 对每个满足 $0 \leq i < N$ 的 $i$，都有 $1 \leq T[i] \leq 4$。

子任务

例子

例 1

考虑以下调用。

max_coupons(13, [4, 500, 8, 14], [1, 3, 3, 4])

Narya 起初有 $A = 13$ 枚代币。她可以按以下顺序购买 $3$ 张礼券：

在这个例子中，Narya 不可能购买多于 $3$ 张的礼券，并且上述购买顺序是她购买这 $3$ 张礼券的唯一方式。因此，该函数应返回 $[2, 3, 0]$。

例 2

考虑以下调用。

max_coupons(9, [6, 5], [2, 3])

在这个例子中，Narya 可以以任意顺序购买两张礼券。因此，该函数可以返回 $[0, 1]$ 或 $[1,0]$。

例 3

考虑以下调用。

max_coupons(1, [2, 5, 7], [4, 3, 1])

在这个例子中，Narya 有 $1$ 枚代币，不足以购买任何一张礼券。因此，该函数应返回 $[\ ]$ （空数组）。

评测程序示例

输入格式：

N A
P[0]  T[0]
P[1]  T[1]
...
P[N-1]  T[N-1]

输出格式：

S
R[0]  R[1]  ...  R[S-1]

其中，$S$ 是 max_coupons 返回的数组 $R$ 的长度。