#P16929. [SGU313]Circular Railway

    ID: 16137 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>数学算法基础排序贪心构造数据结构栈CF2200

[SGU313]Circular Railway

题目描述

有一条环形铁路,共有 LL 个车站,编号为 1,2,…,L1,2,\ldots,L。列车可以沿两个方向运行,相邻车站之间的行驶时间均为 11 分钟,其中车站 LL 与车站 11 也相邻。

铁路沿线有 nn 名员工的住宅和 nn 个办公室。每个住宅和办公室都位于某个车站附近。

现在需要在住宅与办公室之间建立一个一一对应关系:每名员工被分配到一个不同的办公室。员工从住宅所在车站前往办公室所在车站时,总是选择环形铁路上的较短方向。

请安排这种一一对应关系,使所有员工的总通勤时间最小,并输出这个最小值。

输入格式

第一行包含两个整数 n,Ln,L:

  • 1≤n≤500001\le n\le 50000;
  • 2≤L≤1092\le L\le 10^9。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 表示第 ii 名员工住宅所在的车站编号。

第三行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n,其中 bib_i 表示第 ii 个办公室所在的车站编号。

所有位置均满足 1≤ai,bi≤L1\le a_i,b_i\le L。多个住宅或办公室可以位于同一个车站。

输出格式

输出一行一个整数,表示所有员工总通勤时间的最小可能值。

样例 1

3 15
1 2 10
11 12 13
9

样例 2

4 12
2 5 8 11
6 9 12 3
4

说明

两车站 x,yx,y 之间的通勤时间为

min⁡(∣x−y∣,L−∣x−y∣)\min(|x-y|,L-|x-y|)。

答案可能超过 32 位有符号整数范围,请使用 64 位整数保存答案。