SP2485 PHONELIN - Phone Lines
题目描述
在一条直线上分布着若干城市和信号塔。可以通过支付一定费用将信号塔设置为可接受连接的状态。我们得到了这些信号塔和城市的 X 轴坐标。我们的任务是选择一定数量的塔设为可接受连接，以此来获取最大利润。
具体规则如下：每个城市在成功发送数据到某个塔后，会根据公式**D - 数据传输距离**向你支付费用，其中，数据传输距离指的是城市位置和塔位置之间的差值。如果某个塔不在范围 D 内，或者没有设置为可接受连接的状态，城市将无法发送数据，并立即停止，不再继续尝试其他塔。
每个城市在选择信号塔时按以下算法操作：
1. 找到该城市左侧最近的信号塔。
2. 如果该塔位于范围 D 内且设置为可接受连接，城市就将数据发送到这个塔。如果超出范围或者塔未接受连接，则城市停止发送。
3. 如果数据发送成功，城市会：
1. 跳过接下来的三个塔（无论这些塔是否能接受连接）。
2. 尝试将数据发送到跳过的三个塔之后的第四个塔，使用步骤2的方法再进行判断。
输入格式
输入由多个测试用例组成。每个测试用例的第一行包含三个整数：D、C 和 T，分别表示数据传输的最大范围、城市的数量和信号塔的数量。第二行包含 C 个整数，表示各城市的 X 轴位置。接下来的 T 行每行包含两个整数：location[i] 表示第 i 个塔的位置和 connection-cost[i] 表示将塔设为可接受连接的费用。输入以一行 "-1 -1 -1" 结束。
输出格式
对于每个测试用例，输出一行，给出可以获取的最大利润。
说明/提示
- 任意两个点（信号塔或城市）不会具有相同的 X 坐标。
- $T, C \le 100$。
### 样例输入
```
4 9 6
23
43
18
15
29
50
41
31
40
32 2
26 0
46 7
48 0
50 3
38 1
-1 -1 -1
```
### 样例输出
```
5
```
**本翻译由 AI 自动生成**