abrupt

Colegiul Național “Frații Buzești”
Centrul de Pregătire pentru Performanță în Informatică
InfoCNFB - Ediția a II-a, Juniori
9 decembrie 2023

Cerință

Se dau două șiruri $A$ și $B$, ambele cu câte $n$ elemente, ordonate crescător. Se mai dă un număr $m$. Dorim să construim un șir $C$ cu $m$ elemente cu următoarele proprietăți:

• să fie crescător;
• să existe o valoare $p$ ($1 \leq p \lt m$), astfel încât primele $p$ elemente din $C$ să formeze secvență în $A$, iar ultimele $m-p$ elemente din $C$ să formeze o secvență din $B$;
• considerând $D$ șirul cu cele $m-1$ diferențe a câte doi termeni consecutivi din $C$ (în valoare absolută), valoarea cea mai mare din $D$ să fie maxim posibilă.

Date de intrare

Fișierul abrupt.in conține pe prima linie numerele $n$ și $m$, separate prin spațiu. Pe linia a doua se află $n$ numere naturale, în ordine crescătoare, separate prin spațiu, reprezentând elementele șirului $A$. Pe linia a treia se află $n$ numere naturale, în ordine crescătoare, separate prin spațiu, reprezentând elementele șirului $B$.

Date de ieșire

Fișierul abrupt.out va conține un singur număr natural reprezentând valoarea maximă din șirul $D$.

Restricții și precizări

• $1 \leq n \leq 300 \ 000$;
• $2 \leq m \leq 2 \times n$;
• Elementele șirurilor $A$ și $B$ sunt naturale cel mult egale cu $2 \ 000 \ 000 \ 000$;
• Pentru $20$ de puncte, $n \leq 50$;
• Pentru $40$ de puncte, $n \leq 200$;
• Pentru $60$ de puncte, $n \leq 2 \ 000$;

Exemplu

abrupt.in

3 4
2 6 7
3 8 9

abrupt.out

5

Explicație

Putem forma șirul $C$ astfel: $2 \ 3 \ 8 \ 9$. Șirul $D$ ar avea valorile $1 \ 5 \ 1$.