学步园

世博会正在如火如荼的举行中，dandelion和她的朋友也打算好好游览一番，不过由于经费有限，她们只能去园区游览一天。经过全方位调研，她们得到了园区的展厅分布图。

园区是一个圆形，共有n个展厅，每个展厅都有不同的主题（一共有m种主题），有舞蹈表演的，有传统工艺展示的，有高新科技展示的等等，现在dandelion和她的朋友想知道，假设她们可以随机选取一个展厅为起点，她们至少要经过多少距离才能参观完所有主题。

输入

第一行是case数T(1<=T<=50)，接下来有T组数据。

对于每组数据，第一行有3个整数n, m, t(2 <= n <= 1000000, 1 <= m <= 100, 0 < t < 2³¹) t 表示圆区的周长。

接下去m行，每行以一个整数k开始，(1 <= k <= n)表示该种主题的展厅有k个，接下去有k个递增整数Li （0 <= Li < t），表示该展厅距离1号展厅的顺时针距离。

输出

输出dandelion要参观所有主题的场馆要走的最短距离。

样例输入

1
3 2 80133375
2 0 24951291
1 49140546

样例输出

24189255

模拟题

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node
{
	int dist;
	int sub;
}pos[1000001];

int cmp(const void *a, const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;
	return aa->dist - bb->dist;
}

int main()
{
	int test;
	int n, m, sum;
	int view[100];
	int i, j, num, count, dist;
	int s, t, temp, min;

	scanf("%d", &test);
	while(test--)
	{
		scanf("%d %d %d", &n, &m, &sum);
		count = 0;
		for (i = 0; i < m; ++i)
		{
			scanf("%d", &num);
			for (j = 0; j < num; ++j)
			{
				scanf("%d", &dist);
				pos[count].dist = dist;
				pos[count].sub = i;
				++count;
			}
		}
		qsort(pos, n, sizeof(pos[0]), cmp);
		
		s = 0;
		t = -1;
		memset(view, 0, sizeof(view));
		min = 0x7fffffff;
		while(s < n)
		{
			for (i = 0; i < m; ++i)
				if (view[i] == 0)
					break;
			if (i < m)
			{
				++t;
				++view[pos[t % n].sub];
			}
			else
			{
				temp = pos[t % n].dist - pos[s].dist;
				if (t >= n)
					temp += sum;
				if (min > temp)
					min = temp;
				--view[pos[s].sub];
				++s;
			}
		}
		printf("%d\n", min);
	}
	return 0;
}