题目描述

给定一张 $n$ 个点的有向完全图和一个整数 $m$，节点 $u$ 有两个参数 $a_u$ 和 $b_u$，$u\rightarrow v$ 的边权为 $(a_u+b_v)\mod\ m$，求 $1$ 到 $n$ 的最短路长度。

输入格式

第一行两个整数 $n,m$

第二行 $n$ 个整数，表示 $a_1,a_2,...,a_n$

第三行 $n$ 个整数，表示 $b_1,b_2,...,b_n$

输出格式

一行一个整数，表示答案。

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

数据范围

$$\begin{aligned} &\bullet \ 2 \le n \le 2 \times 10^5 \\ &\bullet \ 2 \le m \le 10^9 \\ &\bullet \ 0 \le a_i,b_i < m \\ \end{aligned}$$