### 问题描述 农夫有一块 $10^9\times 10^9$ 的荒地，分为 $10^9 \times 10^9 $ 个小方格（行为 $10^9$，列为 $10^9$），他打算对这片地进行整顿，使其适于种植。 该荒地需要整顿的地方在于，其行与行之间，列于列之间存在许多废弃的藩篱，需要农夫清理。藩篱分为两种： - 列的无限藩篱：在列 $x$ 与列 $x+1$ 之间有一道藩篱，长度为无限长。 - 行的有限藩篱：在行 $y$ 与行 $y+1$ 之间有一道藩篱，其起止长度为从列 $x_1$ 到列 $x_2$（包括 $x_1,x_2$）。 农夫要对这块地进行检查。农夫初始时从坐标为 $(1,1)$ 的方格出发，他打算到达第 $10^9$ 行的任意一个位置。按农夫的走路规则，若没有藩篱阻挡，农夫可以到达他当前所在行和列的任意一个位置，若有藩篱阻挡，则农夫无法通过藩篱。 农夫可以选择完全拆除任意一块藩篱。拆除某种藩篱所需的成本均为 $s$。 农夫想请你帮他求出，农夫完成本次检查所需的最少成本是多少。 ### 输入格式 输入第一行包含三个整数 $n,m,s$，分别表示列的无限藩篱的个数，行的有限藩篱的个数，以及拆除一个藩篱的成本。 接下来 $n$ 行每行包含一个整数 $x$，表示在列 $x$ 与列 $x+1$ 之间有一道列的无限藩篱。 接下来 $m$ 行每行包含三个整数 $x_1,x_2,y$，在行 $y$ 与行 $y+1$ 之间有一道行的有限藩篱，其起止长度为从列 $x_1$ 到列 $x_2$（包括 $x_1,x_2$）。 ### 输出格式 输出一个整数，表示农夫完成本次检查的最小成本。 ### 样例输入 ``` 1 3 7 4 1 5 3 1 9 4 4 6 6 ``` ### 样例输出 ``` 7 ``` ### 评测数据规模 对于所有评测数据，$0\leq{n,m}\leq{10^5 },1\leq{x}\leq{10^9 },1\leq{x_1}\leq{x_2}\leq{10^9 },1\leq{y}\leq{10^9 },1\leq{s}\leq{10^9 }$。