SP3308 BRIDGES2 - The Bridges of San Mochti

你在圣莫奇丛林的一个军事训练基地工作，其中有一项训练任务是穿越一系列高悬在树间的绳索桥。每座桥都有其最大承载人数，这是指在不破裂的情况下桥能同时承载的最多人数。目标是在满足以下战术要求的前提下，尽可能快地通过所有桥梁： _一次一队！_如果桥的容量允许，两个或更多的人可以同时过桥，他们以一个整体行进，步调一致。绝不能同时有两个不同的队伍在一座桥上，即便这样不会超过桥的最大承载能力。多队伍同时过桥不符合战术要求，可能引起绳索振动，影响速度。这个规则即使在队伍仅有一人时也适用。_保持前进！_当一座桥空闲时，要尽可能多的人立即组成一个队伍过桥。请注意，这种策略不一定总能实现最短的过桥总时间（例如，等后面更多的人赶上可能更快），但从战术角度考虑，等待并不明智，因为可能等的人无法赶到，这不仅浪费时间，还可能危及自身安全。桥梁的配置会定期更新以提供新的挑战。给定一种桥梁配置，你需要求出在这些限制下所有人通过所有桥梁所需的最短时间。 例如，假设有九个人需要通过两座桥：第一座桥允许最多 3 人同时过桥，需耗时 10 秒；第二座桥最多 4 人同时过桥，耗时 60 秒。初始状态为 (9 0 0)，表示 9 个人在等待通过第一座桥，没有人在等待通过第二座桥，也没有人已经完全通过桥。经过 10 秒，状态为 (6 3 0)。20 秒时状态变为 (3 3 /3:50/ 0)，这里 /3:50/ 表示有 3 人正在通过第二座桥，还需 50 秒；30 秒时状态为 (0 6 /3:40/ 0)；在 70 秒时状态变为 (0 6 3)；到 130 秒时为 (0 2 7)，最后在 190 秒时为 (0 0 9)。因此总的最短时间为 190 秒。

输入包含一个或多个桥梁配置，以一行"两个零"结束。每个桥梁配置以一行开始，其中包含一个负整数 -$B$ 和一个正整数 $P$，表示桥梁数 $B$ 和总过桥人数 $P$。$B$ 和 $P$ 最大为 20。（负数 -$B$ 被用于使配置的第一行更显著）。接下来有 $B$ 行，每行定义一座桥梁，从需首先通过的桥梁到最后的顺序列出。每座桥由两个正整数 $C$ 和 $T$ 定义，分别表示桥的最大容量和通过所需时间（秒）。$C$ 最大为 5，$T$ 最大为 100。每次只能有一个队伍，且人数不超过 $C$，通过桥梁；无论队伍人数，所需时间始终为 $T$。桥与桥之间没有经过的时间。

对每个桥梁配置，输出一行，表示所有人按照要求通过所有桥梁所需的最短时间（秒）。

$1 \le B \le 20, 1 \le P \le 20, 1 \le C \le 5, 1 \le T \le 100$。 **本翻译由 AI 自动生成**