Hasarın arxasında (Qızıl)#10588

Hasarın arxasında (Qızıl)

1 saniyə

128 meqabayt

Çətin

Fermer Con onun bir çox inəyinin nədənsə aqorafobiyadan (yəni böyük açıq məkanlardan qorxmaqdan) əziyyət çəkdiyini fərq etdi. İnəklərin otlamaqdan daha az qorxması üçün o, öz böyük tarlasını şaquli (şimal-cənub) və üfüqi (şərq-qərb) hasarlar quraraq bir neçə kiçik sahəyə bölür.

Böyük tarla künc nöqtələri $(0, 0)$ və $(a, b)$ olan düzbucaqlı formasındadır. Fermer Con müxtəlif $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a) mövqelərində $n$ şaquli hasar qurur, onların hər biri $(a_{i}, 0)$ (a_i, 0) nöqtəsindən $(a_{i}, b)$ (a_i, b) nöqtəsinə qədər uzanır. O, həmçinin $b_{1}, \dots, b_{m} (0 < b_{i} < b)$ b_1, \ldots, b_m~(0 < b_i < b) mövqelərində $m$ üfüqi hasar qurur, onların hər biri $(0, b_{i})$ (0, b_i) nöqtəsindən $(a, b_{i})$ (a, b_i) nöqtəsinə qədər uzanır. Hər bir şaquli hasar hər bir üfüqi hasarı kəsir, böyük tarlanı cəmi $(n + 1) (m + 1)$ (n + 1)(m + 1) sahəyə bölür.

Təəssüf ki, Fermer Con hasarlarında qapı düzəltməyi tamamilə unudub, buna görə də inəklər öz hasarlanmış sahələrindən çıxıb bütün tarla boyunca hərəkət edə bilmirlər! O, bu vəziyyəti düzəltmək üçün bəzi hasarların hissələrini aradan qaldıraraq inəklərin qonşu sahələr arasında hərəkət etməsinə imkan yaratmaq istəyir. O, qonşu sahələrin müəyyən cütlərini seçib onları ayıran hasar hissəsini tamamilə aradan qaldırmaq istəyir. Bundan sonra o, inəklərin əmələ gələn boşluqlardan keçərək böyük tarlanın istənilən nöqtəsinə hərəkət edə bilməsini istəyir.

Məsələn, Fermer Con hasarların aşağıdakı düzülüşü ilə başlaya bilər:

+---+--+
|   |  |
+---+--+
|   |  |  
|   |  |
+---+--+

və keçidləri aşağıdakı kimi aça bilər:

+---+--+
|      |  
+---+  +  
|      |  
|      |
+---+--+

Fermer Cona öz məqsədinə çatmaq üçün aradan qaldırılması lazım olan hasarların minimum ümumi uzunluğunu müəyyən etməkdə kömək edin.

Giriş

Birinci sətirdə dörd tam ədəd verilir: $a, b (1 \leq a, b \leq 1 0^{9})$ a, b~(1 \le a, b \le 10^9), $n (0 \leq n \leq 2000)$ n~(0 \le n \le 2000) və $m (0 \leq m \leq 2000)$ m~(0 \le m \le 2000). Sonrakı $n$ sətirdə $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a) qiymətləri, sonrakı $m$ sətirdə isə $b_{1}, \dots, b_{m} (0 < b_{i} < b)$ b_1, \ldots, b_m~(0 < b_i < b) qiymətləri verilir.

Çıxış

Fermer Conun aradan qaldırmalı olduğu hasarların minimum ümumi uzunluğunu çıxarın. Nəzərə alın ki, bu qiymət standart $32$ -bitlik tam ədəd tipinə sığmayacaq qədər böyük ola bilər, buna görə də $64$ -bitlik tam ədəd tipindən istifadə etmək lazım ola bilər.

Nümunələr

Nümunə 1