TX202609 自动售货机

题目描述

学校新安装了一台自动售货机。机器中有 N 种商品，第 i 种商品的单价为 p_i 元，初始库存为 s_i 件。

机器只使用面值为 1 元、5 元和 10 元的硬币。开始时，机器现金箱中这三种硬币的数量分别为 c_1、c_5、c_10。

机器还维护一个“当前余额”，初始为 0。当前余额表示用户已经投入但尚未用于购买或退回的金额。

接下来会发生 Q 次操作。请严格按照以下规则执行。

1. 投币：ADD v

用户投入一枚面值为 v 的硬币，其中 v 只可能为 1、5、10。

• 这枚硬币立即进入现金箱；
• 当前余额增加 v；
• 操作一定成功。

2. 购买：BUY i

用户尝试购买一件第 i 种商品。

如果该商品库存大于 0，并且当前余额不少于 p_i，则：

• 商品库存减少 1；
• 当前余额减少 p_i；
• 操作成功。

否则操作失败，机器状态完全不变。

购买成功时，现金箱中的硬币数量不变，也不会自动退回剩余余额。

3. 退币：CANCEL

用户要求退回全部当前余额。

机器必须使用现金箱中现有的硬币，准确退回该金额：

• 如果存在退币方案，选择硬币总枚数最少的方案；
• 如果最少枚数方案不止一种，优先选择使用 10 元硬币更多的方案；仍相同时，优先选择使用 5 元硬币更多的方案；
• 操作成功后，从现金箱中取走退回的硬币，并将当前余额清零；
• 如果无法准确退回全部余额，则操作失败，机器状态完全不变。

当前余额为 0 时，退币操作成功，不取走任何硬币。

对于每次操作，输出操作是否成功以及操作结束后的当前余额。最后输出各商品的剩余库存。

输入格式

第一行包含两个正整数 N 和 Q，分别表示商品种类数和操作次数。

接下来 N 行，每行包含两个整数 p_i 和 s_i，分别表示商品单价和初始库存。

接下来一行包含三个非负整数 c_1、c_5、c_10，表示现金箱中三种硬币的初始数量。

接下来 Q 行，每行是一条操作，格式为：

ADD v
BUY i
CANCEL

保证所有操作名称合法，且 BUY 中的商品编号合法。

输出格式

前 Q 行，每行输出一个字符串和一个整数，用空格分隔：

• 操作成功，输出 OK；
• 操作失败，输出 FAIL；
• 整数表示此次操作结束后的当前余额。

最后一行输出 N 个整数，依次表示各商品的剩余库存。

样例输入

2 8
6 1
4 2
4 1 0
ADD 10
BUY 1
CANCEL
BUY 1
ADD 5
BUY 2
CANCEL
BUY 2

样例输出

OK 10
OK 4
OK 0
FAIL 0
OK 5
OK 1
FAIL 1
FAIL 1
0 1

样例说明

第一次退币时，机器使用四枚 1 元硬币退回余额 4 元，现金箱中的 1 元硬币用完。

第二次购买第 1 种商品时，该商品已经没有库存，因此购买失败。

购买第 2 种商品后，余额为 1 元。此时现金箱中没有 1 元硬币，无法准确退币，所以退币失败，余额仍为 1 元。

最后一次购买因余额不足而失败。

数据范围

• 1 ≤ N ≤ 10^5
• 1 ≤ Q ≤ 2 × 10^5
• 1 ≤ p_i ≤ 10^9
• 0 ≤ s_i ≤ 10^9
• 0 ≤ c_1, c_5, c_10 ≤ 10^9

子任务如下，各子任务独立计分：