题目描述

为了布置舞台背景，你需要在一条直线上等间距摆放三棵人造圣诞树，依次记为 $A,B,C$。相邻两棵树之间的距离均为 $d$ 厘米。

每棵树由一根竖直树干和若干块三角形泡沫板组成。对于第 $i$ 棵树，它的所有泡沫板形状完全相同，都是等腰三角形：

• 高为 $s_i$ 厘米；
• 底边宽为 $2s_i$ 厘米。

每根树干上有若干预先确定的安装位置，其高度以相对于树底部的海拔 $y_{i,j}$ 表示。为了让圣诞树看起来尽可能茂盛，你希望安装的泡沫板总面积尽可能大。

但是，任意两块三角形泡沫板都不能发生面积为正的重叠；它们可以只在边界上接触。

请从所有可安装的泡沫板中选择一个子集，使其互不重叠，并最大化总面积。

两组样例的圣诞树布置示意图

输入格式

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

随后依次给出树 $A,B,C$ 的描述。每棵树包含两行：

• 第一行包含两个整数 $n_i,s_i$（$1\le n_i\le 100$，$1\le s_i\le d$），分别表示可安装位置数和该树三角形泡沫板的高度；
• 第二行包含 $n_i$ 个整数 $y_{i,1},y_{i,2},\ldots,y_{i,n_i}$（$0\le y_{i,j}\le 10^7$），表示所有可安装位置的高度。

输入中的安装高度不保证有序。

输出格式

输出能够安装的三角形泡沫板的最大总面积。

由于一块高为 $s_i$、底边宽为 $2s_i$ 的三角形面积为 $s_i^2$，答案一定是整数。

样例 1

输入

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

输出

43

样例 2

输入

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

输出

40