30084번 - Kubeliai 다국어

Turime dvi detales, sudarytas iš mažų kubelių. Abi detalės yra $1$ kubelio pločio ir $2$ kubelių aukščio. Pirmosios detalės viršutinioji eilė ir antrosios detalės apatinioji eilė yra pilnai užpildytos, pavyzdžiui:

Keliais būdais šias detales galima pastatyti vieną ant kitos taip, kad detalės liestųsi ir bendras aukštis būtų ne daugiau kaip $3$?

Detalių negalima vartyti ir sukioti, ir bent vienas antros detalės kubelis turi būti po pirma detale.

Paveiksliuke matome pavyzdį, kur viršutinę detalę galime tiesiai nuleisti ant apatinės, taip gaudami galimą konfigūraciją.

Pirmojoje eilutėje pateikti keturi sveikieji skaičiai – pirmosios detalės ilgis $M$, antrosios detalės ilgis $L$, pirmosios detalės apatinės eilės kubelių skaičius $N$ ir antrosios detalės viršutinės eilės kubelių skaičius $K$.

Antrojoje eilutėje pateikiama $N$ tarpu atskirtų sveikųjų skaičių $a_i$ – pirmosios detalės apatinės eilės kubelių pozicijos.

Trečiojoje eilutėje pateikiama $K$ tarpu atskirtų sveikųjų skaičių $b_i$ – antrosios detalės viršutinės eilės kubelių pozicijos.

Išveskite vieną skaičių – kiek yra būdų šias detales sustatyti vieną ant kitos taip, kad detalės liestųsi ir bendras aukštis būtų ne daugiau kaip $3$.

• $1 ≤ M, L ≤ 10^9$
• $1 ≤ N, K ≤ 1\,000$
• $1 ≤ a_i < a_j ≤ M$ ($1 ≤ i < j ≤ N$)
• $1 ≤ b_i < b_j ≤ L$ ($1 ≤ i < j ≤ K$)