题目链接

题意

已知 $n$ 个点，第 $i$ 个点有两个属性 $a_i,b_i$。

对于 $1\le i,j\le n$，第 $i$ 个点向第 $j$ 个点连了一条有向边，代价为 $(a_i+b_j)\mod M$。

求 $1$ 号节点到 $n$ 号节点的最短路。

输入格式

第一行两个数 $n,M$。

第二行 $n$ 个数，第 $i$ 个数表示 $a_i$。

第三行 $n$ 个数，第 $i$ 个数表示 $b_i$。

输出格式

一行一个数，表示答案。

样例

4 12
10 11 6 0
8 7 4 1

3

10 1000
785 934 671 520 794 168 586 667 411 332
363 763 40 425 524 311 139 875 548 198

462

数据范围

$2\le n\le 2\times 10^5$

$2\le M\le 10^9$

$0\le a_i,b_i\le M$