Description

你现在位于珠穆朗玛峰顶，想要体验山顶上所有美丽的徒步路线。然而，根据以往的经验，你知道独自在珠穆朗玛峰上攀爬是很危险的——你可能会在黑暗中迷路！因此，你希望在预定的时间与导游一起参加徒步旅行。

山上共有 $\mathbf{C}$ 个营地（编号为 $1$ 到 $\mathbf{C}$），共有 $2 \times \mathbf{C}$ 条单向徒步路线（编号为 $1$ 到 $2 \times \mathbf{C}$）。每条徒步路线从一个营地出发，终点为另一个不同的营地，中间不会经过其他营地。珠穆朗玛峰人烟稀少，生意也很冷清；每个营地恰好有 2 条徒步路线出发，也恰好有 2 条徒步路线到达。

每条徒步路线每天都会运行。第 1 条和第 2 条路线从营地 1 出发，第 3 条和第 4 条路线从营地 2 出发，依此类推：一般来说，第 $2 \times i - 1$ 条和第 $2 \times i$ 条路线从营地 $i$ 出发。第 $i$ 条徒步路线终点为营地编号 $\mathbf{E}_i$，出发时间为第 $\mathbf{L}_i$ 小时，持续时间恰好为 $\mathbf{D}_i$ 小时。

现在是第 0 小时；一天中的小时编号为 $0$ 到 $23$。你位于营地 1，想要每条徒步路线都走一次，并最终回到营地 1。你不能通过其他方式在营地之间移动，只能乘坐徒步路线。在营地时，你可以等待任意小时数（包括 0），但只能在徒步路线出发的那一刻登上路线。

在查看了所有路线的时间表后，你已经确定一定可以实现目标，但你希望用最短的时间完成。如果你合理规划路线，完成所有徒步路线所需的最短时间是多少小时？

Input Format

输入的第一行是测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据的第一行为一个整数 $\mathbf{C}$，表示营地数量。接下来有 $2 \times \mathbf{C}$ 行，第 $i$ 行（从 1 开始计数）描述一条徒步路线，其起点为营地编号 $\text{floor}((i + 1) / 2)$，包含三个整数 $\mathbf{E}_i$、$\mathbf{L}_i$ 和 $\mathbf{D}_i$，含义如上所述。注意，这种输入格式保证每个营地恰好有两条路线出发。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是完成所有路线所需的最短小时数。

2
2
2 1 5
2 0 3
1 4 4
1 6 3
4
3 0 24
2 0 24
4 0 24
4 0 24
2 0 24
1 0 24
3 0 24
1 0 24

Case #1: 32
Case #2: 192

Hint

在样例 1 中，最优方案如下：

• 在营地 1 等待 1 小时，直到第 1 小时。
• 在第 1 小时从营地 1 出发，乘坐 5 小时的徒步路线，到达营地 2，此时为第 6 小时。
• 立即在第 6 小时从营地 2 出发，乘坐 3 小时的徒步路线，到达营地 1，此时为第 9 小时。
• 在营地 1 等待 15 小时，直到第二天的第 0 小时。
• 在第 0 小时从营地 1 出发，乘坐 3 小时的徒步路线，到达营地 2，此时为第 3 小时。
• 在营地 2 等待 1 小时，直到第 4 小时。
• 在第 4 小时从营地 2 出发，乘坐 4 小时的徒步路线，到达营地 1，此时为第 8 小时。

这样总共用时 1 天 8 小时，即 32 小时。任何其他方案都更慢。

在样例 2 中，所有路线的出发时间和持续时间都相同。完成任意一条路线后，你都可以立即乘坐另一条路线。如果我们按输入顺序编号路线为 1 到 8，一种最优方案为：$1, 5, 4, 7, 6, 2, 3, 8$。

数据范围

• $1 \leq \mathbf{T} \leq 100$。
• $1 \leq \mathbf{E}_i \leq \mathbf{C}$。
• 对所有 $i$，有 $\mathbf{E}_i \neq \text{ceiling}(i / 2)$（没有路线起点和终点相同）。
• 对所有 $j$，有 $\text{size of } \{j : \mathbf{E}_j = i\} = 2$（每个营地恰好有两条路线到达）。
• $0 \leq \mathbf{L}_i \leq 23$。
• $1 \leq \mathbf{D}_i \leq 1000$。
• 至少存在一条从营地 1 出发、最终回到营地 1、且每条路线恰好走一次的路线。

小数据范围（6 分，测试点 1 - 可见）

• $2 \leq \mathbf{C} \leq 15$。

大数据范围（24 分，测试点 2 - 隐藏）

• $2 \leq \mathbf{C} \leq 1000$。

由 ChatGPT 4.1 翻译