#P18723. Buy for More, Sell for Less
Buy for More, Sell for Less
Buy for More, Sell for Less
题名没有笔误。
Monocarp 是一个非常奇怪的人:购买物品会让他感到快乐,即使后来卖出的价格低于买入价格。每购买一件物品,他获得 单位快乐。
有 种物品,第 种的买入价和卖出价分别为整数 ,满足 。最初 Monocarp 有一定数量的硬币,可以反复执行以下操作:
- 如果当前至少有 枚硬币,可以花费 枚硬币购买一件第 种物品。每种物品的库存均为无限。
- 如果持有至少一件尚未售出的第 种物品,可以卖出其中一件,获得 枚硬币。
处理 次独立查询。第 次查询给出初始硬币数 ,求 Monocarp 最多能获得多少快乐。
输入格式
第一行包含整数 ,满足 、。
第二行包含 个整数 ,满足 。
第三行包含 个整数 ,满足 。
第四行包含整数 ,满足 。
查询序列按下述方式生成,并非直接写在输入中:
-
令 ,,对 ,令
-
令 , 表示第 次查询的正确答案。
-
对 ,令
因此 可以为 。每次查询都重新开始,只以上一次查询的答案参与序列生成,不继承上一次查询的硬币或物品。
输出格式
输出一行一个整数:
$$c_1\mathbin\oplus c_2\mathbin\oplus\cdots\mathbin\oplus c_q,$$其中 表示按位异或。
原样例一
4 6
10 3 6 7
8 1 3 4
2 1 4
7
原样例二
7 10
5 8 11 9 10 12 4
2 6 9 8 1 11 1
13 1234567891011 37
16313242560751
原说明
第一个样例的查询为 ,答案分别为 。