#P18858. [Croatian CPC2025] Formidable Formicidae

[Croatian CPC2025] Formidable Formicidae

Formidable Formicidae

题目描述

一条长度为 LL 的带子被分成 LL 个单位格子,从左到右编号为 1,2,…,L1,2,\ldots,L。带子上有 NN 只蚂蚁,最初分别位于格子 a1,…,aNa_1,\ldots,a_N 的中心。

你可以为每只蚂蚁选择初始朝向,向左或向右。开始运动后,所有蚂蚁以每秒一个单位长度的速度移动。两只蚂蚁相撞时,它们立即反向;蚂蚁撞到带子的端点时,也立即反向。转向不消耗时间。

给定 NN 个目标格子 b1,…,bNb_1,\ldots,b_N。求最小的非负整数时间 TT,使得能够选择初始朝向,让 TT 秒后所有蚂蚁恰好占据这些目标格子的中心。无需指定哪只蚂蚁到达哪个目标格子。

如果无法做到,输出 −1-1。

输入格式

第一行包含整数 L,NL,N。

第二行包含 NN 个整数 a1,…,aNa_1,\ldots,a_N。

第三行包含 NN 个整数 b1,…,bNb_1,\ldots,b_N。

输出格式

输出一个整数,表示最短时间;若不存在这样的初始朝向,输出 −1-1。

数据范围

  • 1≤L≤1091\le L\le10^9,1≤N≤30001\le N\le3000。
  • 1≤ai,bi≤L1\le a_i,b_i\le L。
  • 所有 aia_i 互不相同,所有 bib_i 也互不相同。

样例 1

输入

4 2
2 4
1 4

输出

1

样例 2

输入

8 4
1 3 6 7
1 3 5 8

输出

2

样例 1 说明

让第一只蚂蚁向左,第二只向右。经过一秒,第一只到达格子 11 的中心;第二只先用半秒到达带子右端点,再用半秒返回格子 44 的中心。