我们正在为一部戏剧的背景布置 3 棵人造圣诞树，它们沿一条直线等距排列。

每棵人造树都由一根垂直的树干和一片或多片相同的三角形泡沫塑料组成，这些塑料片设计用于固定在特定的树干上。第 $i$ 棵树上的所有塑料片都具有完全相同的等腰三角形形状，其底边宽度等于高度的两倍（即 $(2 \cdot s_i) \times (s_i)$ 厘米）。

树干可以在预先定义的安装点上固定三角形，这些安装点由距离树底部的垂直高度决定。为了让这些树在泡沫塑料的装点下显得尽可能生机勃勃，我们希望固定在树上的塑料片面积之和尽可能大。

然而，我们实际可以安装的塑料片集合是有限的，因为我们不希望任何三角形之间发生重叠，除非它们仅在边界上相切。

请寻找一个塑料片子集，在保证所有树上的任何塑料片都不重叠的前提下，使得所使用的塑料片总面积最大。

图 K.1：说明样例 1 和样例 2 的树木排列示意图

求我们可以安装的三角形的最大面积之和。

输入格式

• 第一行包含一个整数 $d$（$1 \le d \le 10^7$），表示树 $A$ 与 $B$ 之间、以及 $B$ 与 $C$ 之间的距离（单位：厘米）。

• 接下来是树 $A$、$B$ 和 $C$ 的三组描述，每组描述包含：

  • 第一行包含第 $i$ 棵树的三角形位置数量 $n_i$ 和三角形尺寸 $s_i$（$1 \le n \le 100$；$1 \le s \le d$）。
  • 第二行包含 $n_i$ 个整数，表示可能的三角形安装高度（单位：厘米） $y_{ij}$（$0 \le y \le 10^7$）。

输出格式

输出树上三角形塑料片的最大可能总面积。

样例

输入样例 1

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

输出样例 1

43

输入样例 2

5
3 2
0 1 2
3 4
0 2 4
3 2
0 1 2

输出样例 2

40