本题没有可用的提交语言。

题目描述

传真图像是由深色和白色像素组成的矩形阵列。上方展示了三个经过高度放大的小示例，以便清晰看到每个像素。你的任务是编写一个程序，计算传真图像中相连的深色像素组件的数量。我们假设，两个在垂直或水平方向上直接相邻的深色像素属于同一个组件。仅在角落对角接触的像素不视为直接相连。例如，传真1中有2个组件，传真2中有3个组件（如下方不同阴影所示）。在传真3中，所有32个深色像素都属于独立组件，因为它们仅在角落接触。
传真图像经过编码以节省传输带宽。假设在实际传真内容上方有一个空白行，那么传真中的每个像素可以标记为与上方像素相同（S）或不同（D），如下图所示。
如果按行优先顺序（从左到右逐行读取，然后向下到下一行）读取S和D标记，那么三个传真的像素标记如下：

• 传真1：SDDSDDSSSDDDSDD
• 传真2：DDDDDDDSSDDDDSSSDSDSSSDSSDSSSSSSDSSSSSSSSSSSSSDSSSDSDDDS
• 传真3：DSDSDSDSDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
  如果我们统计连续出现的S和D的次数（始终从S开始计数，即使开头没有S），则结果如下：
• 传真1：1S 2D 1S 2D 3S 3D 1S 2D
• 传真2：0S 7D 2S 4D 3S 1D 1S 1D 3S 1D 2S 1D 6S 1D 13S 1D 3S 1D 1S 3D 1S
• 传真3：0S 1D 1S 1D 1S 1D 1S 1D 1S 56D

由于S和D的连续段总是交替出现，我们可以省略标记，得到最终编码：

• 传真1：1 2 1 2 3 3 1 2
• 传真2：0 7 2 4 3 1 1 1 3 1 2 1 6 1 13 1 3 1 1 3 1
• 传真3：0 1 1 1 1 1 1 1 1 56

现在，给定传真宽度、编码后的连续段数量和分组方式，你的任务是计算传真中的深色组件数量。需要注意的是，传真可能非常大。

输入格式

输入包含1到24个数据集，最后以仅包含-1的行结束。每个数据集以三个整数w、r、g开始：分别表示传真宽度（像素数）、总连续段数、每行分组的连续段数。三个数均为正数，且满足w ≤ 10^9，r ≤ 1000，g ≤ 40。数据集的剩余部分包含r个连续段长度，每组g个连续段长度占一行，最后一行（可能是唯一一行）的连续段数可能少于g个。每行的数字用空格分隔。第一个连续段长度可以是0，其余均为正数。所有连续段长度不超过10^9。每个传真的总像素数是w的倍数，因此像素构成矩形。输入和输出中的整数不含逗号（题目描述中的逗号仅为便于阅读）。

输出格式

对每个数据集，输出一行整数，表示传真中的深色组件数量。任何输入的传真编码对应的组件数不超过10^9。注意：逐个检查每个像素的解决方案无法在一分钟的时间限制内完成。

输入示例1

5 8 4  
1 2 1 2  
3 3 1 2  
7 21 8  
0 7 2 4 3 1 1 1  
3 1 2 1 6 1 13 1  
3 1 1 3 1  
8 10 10  
0 1 1 1 1 1 1 1 1 56  
-1  

输出示例1

2  
3  
32  

来源

Mid-Central USA 2003