#P7601. [2018年杭电多校]Ringland

    ID: 7614 传统题 3000ms 128MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>贪心计算几何扫描线CF2400数学前缀和排序二分

[2018年杭电多校]Ringland

Ringland

题目描述

Patrick Star found the Ringland! It's marriage season in Ringland! Ringland has a form of a circle's boundary of length LL. There are NN bridegrooms and NN brides, and bridegrooms decided to marry brides. Of course, each bridegroom should choose exactly one bride, and each bride should be chosen by exactly one bridegroom. All objects in Ringland are located on the boundary of the circle, including the capital, bridegrooms' castles and brides' palaces. The castle of the i-th bridegroom is located at the distance aia_i from the capital in clockwise direction, and the palace of the i-th bride is located at the distance bib_i from the capital in clockwise direction. Let's define the inconvenience of a marriage the summary distance of every bride should walk along the circle from her palace to her bridegroom's castle in the shortest direction (in clockwise or counter-clockwise direction). For a matched pair at coordinates ai,bja_i,b_j, the cost is min⁡(∣ai−bj∣,L−∣ai−bj∣)\min(|a_i-b_j|,L-|a_i-b_j|). Minimize the sum over a bijection between bridegrooms and brides. Equal coordinates are allowed, but people at those coordinates are still distinct.

输入格式

The first line contain a integer TT (no morn than 10), the following is TT test case, for each test case : The first line contains two integers NN and LL (1≤N≤5∗105,1≤L≤1091 \le N \le 5 * 10^5, 1\le L \le 10^9) --- the number of bridegrooms and brides and the length of Ringland. The next line contains NN integers, a1,a2,...,ana_1, a_2, ..., a_n (0≤a1≤a2≤...≤an<L0 \le a_1 \le a_2 \le ... \le a_n < L) --- the distances from the capital to the castles of bridegrooms in clockwise direction. The next line contains NN integers, b1,b2,...,bnb_1, b_2, ..., b_n (0≤b1≤b2≤...≤bn<L0 \le b_1 \le b_2 \le ... \le b_n < L) --- the distances from the capital to the palaces of brides in clockwise direction.

输出格式

For each test case print one line, This line contain only one integer, the smallest possible inconvenience of the wedding.

样例输入 1

1
2 5
3 4
0 2

样例输出 1

2