← 返回题目列表

AtCoder · awc0104_c

C. 决定集合地点

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥正在尝试为他的朋友决定见面地点 N 朋友们。他的朋友们都生活在一条数轴上, i第一个好友当前位于坐标处 A_i.

高桥希望所有朋友都聚集在一个整数坐标处 T。每个朋友都可以通过以下方式更改他们当前的坐标 +1 or -1 一次操作,并重复此操作到达目的地 T。的移动成本为 i第一个到达的朋友 T is |A_i - T| 操作。请注意,如果好友的当前位置与 T,该好友不需要移动,移动成本为 0.

但是,有 M “限制点” B_1, B_2, \dots, B_M 在数轴上设置。任何朋友都不能位于限制点。具体来说,好友每次操作后的坐标一定不能是限制点。在输入中保证没有好友当前位置是限制点。另外,目的地 T 作为非限制点的坐标。

由于数轴是一维的,如果好友当前位置之间存在哪怕一个限制点 A_i 和目的地 T (在开区间 (\min(A_i, T),\ \max(A_i, T))),该好友无法绕过限制点,无法到达 T。反之,如果该区间内没有限制点,则该朋友可以达到 T.

每个好友独立移动,多个好友同时在同一坐标也没有问题。

高桥想要在整数坐标中选择 T 不是限制点,所有朋友都可以到达,使总移动成本最小化的点 \displaystyle\sum_{i=1}^{N} |A_i - T|.

如果至少有一个这样的 T 存在,输出最小的总移动成本。如果没有 T 存在,所有好友均可访问,输出 -1.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • -10^9 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • A_i \neq B_j (1 \leq i \leq N,\ 1 \leq j \leq M)
  • A_i 可能包含重复项 (1 \leq i \leq N)
  • 全部 B_j 是不同的 (1 \leq j \leq M)
  • 所有输入均为整数

输入

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M
  • 第一行包含一个整数 N 代表好友数量,一个整数 M 代表限制点数,以空格分隔。
  • 第二行包含整数 A_1, A_2, \dots, A_N 代表好友当前位置,以空格分隔。
  • 第三行包含整数 B_1, B_2, \dots, B_M 代表限制点,以空格分隔。然而,如果 M = 0,未给出第三行。

输出

如果存在一个非限制点且所有好友均可到达的整数坐标,则输出一行中的总移动成本最小。如果不存在这样的坐标,则输出 -1 一行。


示例输入 1

3 1
1 2 4
10

示例输出 1

3

示例输入 2

2 1
0 2
1

示例输出 2

-1

示例输入 3

10 5
12 15 17 11 19 14 13 16 18 12
-100 10 20 50 100

示例输出 3

23

示例输入 4

40 15
1020 1500 1800 1100 1999 1300 1700 1600 1400 1250 1750 1900 1050 1150 1350 1450 1550 1650 1850 1950 1200 1280 1320 1380 1420 1480 1520 1580 1620 1680 1720 1780 1820 1880 1920 1980 1010 1090 1110 1890
-1000000000 -5000 0 999 2000 5000 10000 12345 20000 50000 100000 1000000 10000000 100000000 1000000000

示例输出 4

10239

示例输入 5

1 0
-1000000000

示例输出 5

0