P13658 [CERC 2020] Pickpockets

警察局位于珠宝店巷的最顶端，这对于镇上的扒手生意来说至关重要。警察每天从巷子的顶端开始巡逻，缓慢地向下走，然后再返回顶端，很少在白天到达巷子的底端。警察的习惯有很多规律，因此“大扒手头目”（BPB）可以为假期制定一个聪明的计划。巷子里的商店从底端到顶端依次用连续的整数编号，从 $1$ 开始。对于假期的每一天，BPB 可以保证从巷子底端到某个编号为止的若干商店不会受到警察的干扰。BPB 有许多扒手小队可供调遣，每个小队可以在某一家商店连续工作若干天。并不是所有小队都必须被雇佣。 BPB 是个严厉的头目，他的规则必须严格遵守： - 在每一天的每一家“干净”的商店，必须且只能有一个小队在工作。 - 每个小队一旦开始在某家商店工作，必须在该商店连续工作若干天。 - 如果某一天某家商店不“干净”，则当天该商店不能有小队工作。 - 每个小队不能在两家或更多商店工作。 - 每个小队在整个假期内最多只能被安排一次。 - 每个小队只能在假期期间工作，不能在假期前后工作。 已知每个小队在其整个工作期间能为 BPB 带来一个特定的最小收入。BPB 想要最大化所有被安排小队的最小总收入。他要求你在今天下午 3 点前给出这个数字，不能晚。千万不要让他失望。

第一行包含两个整数 $H$ 和 $T$（$1 \leq H \leq 10^5$，$1 \leq T \leq 16$），分别表示假期的天数和可用小队的数量。第二行包含 $H$ 个整数 $C_k$（$0 \leq C_k \leq 10^5$，$1 \leq k \leq H$），第 $k$ 天编号不超过 $C_k$ 的商店是“干净”的。$C_k=0$ 表示第 $k$ 天没有“干净”的商店。接下来的 $T$ 行，每行包含两个整数 $D_t$ 和 $I_t$（$1 \leq D_t \leq H$，$0 \leq I_t \leq 10^6$），分别表示第 $t$ 个小队可以连续工作的天数和该小队能带来的最小收入。

输出所有被安排小队的最小总收入的最大值。如果无法满足 BPB 的所有条件，则输出 $0$。

由 ChatGPT 4.1 翻译