草 莓

【题目背景】

尽管不少人都吃过鲜美的草莓，却很少有人真正观察过野草莓的生长。它们从自己的枝上伸出一根根长长的触须，遇到合适的地方就会扎根发芽，长出一株新的草莓。所以，当你在森林中遇到一株草莓的时候，通常就意味着你会在它的周围找到一片草莓田。但这些草莓并非能够无忧无虑地生长，树林中穿梭的鸟儿和偶尔路过的鹿群都喜欢吃这种美味的浆果。不过，草莓最大的威胁却是来自那些贪吃的棕熊。他们不但可以吃掉整整一片草莓，而且还会粗鲁地把一片草莓田搞得乱七八糟。于是每当一块草莓田越长越大之后，森林中的精灵们就会把这片草莓田分成k块种到k个空地中去，以免被粗鲁的棕熊搞乱。她们希望每块空地上恰好放上一块用触须连接在一起的草莓田。不过，如果一块空地里的草莓太少，它们就会感到孤单，所以精灵们希望无论哪块空地含有草莓的总重量都不要太小。可是天真的精灵并不知道怎样来做这件事情，你可以帮助她们吗？

【任务描述】

定义：sum_i表示第i块草莓田中所有草莓重量的和（1£ i£ k）。

你的任务就是要把一片草莓田分割成k块，且分割方案需要满足如下的条件：

l        每一块中的草莓必然是通过触须直接或者间接和其他草莓相连接的；

l        这种分割方案所对应的x尽可能的大。

最后输出你的分割方案和结果。

【输入说明】

第一行为三个整数n、m及k，n表示草莓的株数，m表示触须的数目，k为空地的数目。

接下来的n行每行两个整数i及b_i，表示第i株草莓的重量是b_i克。顺序下来的m行每行两个整数p和q，表示第p株草莓和第q株草莓之间有一根触须相连接。

另外，在所有这些数据的最后还有单独的一行包括一个整数d用作评分系数，有关d的说明，可以参看下面的评分方法。

【输出说明】

你一共要输出k+1行。第一行为一个整数，表示你的分割方案中的x。接下来的k行，每行表示一块草莓田。每行的第一个整数为n_i，表示第i块田中的草莓株数。第二个到第n_i+1个整数为这些草莓的编号。请注意，这些草莓必然是通过触须相连接的。

【输入样例】

7 9 3

1 4

2 4

3 3

4 1

5 5

6 7

7 2

1 2

1 6

2 3

2 5

2 6

4 5

4 6

4 7

6 7

2000000000

 

【输出样例】

7

2 1 6

2 2 3

3 4 5 7

【评分方法】

本题是一道提交答案式题目，你需要针对给定的10个输入文件2/berry1.in~2/berry10.in提交你的输出文件berry1.out~berry10.out（放在你的选手目录下）。我们将根据你提交的输出文件评分。对于某一确定的测试点来说，如果你的输出文件中第一行的x和下面的分割方案不符合，或者是输出文件本身就有错误，那么你将得不到该测试点的分数。这里输出文件的错误可以使用我们提供的2/berry_check检查工具进行检查。只有当这个程序输出Yes的时候，你的输出才可以确认是可接受的。

对于可接受的输出，评分公式如下：

这里d为评分系数（输入数据中最后一行的整数），best为我们的最优结果。

注意：可接受的输出不一定能够得分。

【你如何测试自己的输出】

我们提供2/berry_check这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是：

2/berry_check <输入文件名> <输出文件名>

在你调用这个程序后，2/berry_check将根据你给出的输入和输出文件给出测试的结果，其中包括：

l        非法退出：未知错误；

l        not connect：你程序输出的行中含有不连通的分量；

l        duplicate：同一点输出了两次；

l        extra：输出文件中包括多余数据；

l        lack：输出的总点数不对；

l        answer not match：输出中第一行的x和实际结果不符；

l        Yes：输出可接受，将进行下一步的评分。