Hasarın arxasında (Platin)#10590

Hasarın arxasında (Platin)

1 saniyə

128 meqabayt

Çox çə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 otlaqda daha az qorxması üçün o, öz böyük tarlasını şaquli (şimal-cənub) və üfüqi (şərq-qərb) hasarlar quraşdıraraq bir neçə kiçik sahəyə bölür.

Böyük tarla $(0, 0)$ və $(a, b)$ künc nöqtələrinə malik düzbucaqlı formasındadır. Fermer Con $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a) müxtəlif mövqelərində $n$ şaquli hasar quraşdırır; hər hasar $(a_{i}, 0)$ (a_i, 0) nöqtəsindən $(a_{i}, b)$ (a_i, b) nöqtəsinə qədər uzanır. Həmçinin o, $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 quraşdırır; belə hər hasar $(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 şaquli hasar hər üfüqi hasarla kəsişərək böyük tarlanı ümumilikdə $(n + 1) \times (m + 1)$ (n + 1) \times (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 əhatə olunmuş sahələrini tərk edib bütün tarla boyunca hərəkət edə bilmirlər! O, bu vəziyyəti düzəltmək istəyir — bunun üçün bəzi hasarların hissələrini götürərək inəklərin qonşu sahələr arasında hərəkət etməsinə imkan yaratmaq lazımdır. O, müəyyən qonşu sahə cütləri seçmək və onları ayıran hasar hissəsini tamamilə götürmək istəyir. Bundan sonra o, inəklərin əmələ gələn keçidlərdən keçərək böyük tarlanın istənilən nöqtəsinə sərbəst şəkildə hərəkət edə bilməsini istəyir.

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

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

və keçidləri belə aça bilər:

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

Fermer Cona məqsədinə çatmaq üçün silinməli olan hasarların minimal ümumi uzunluğunu tapmaqda kömək edin.

Giriş

Birinci sətirdə dörd tam ədəd — $a, b (1 \leq a, b \leq 1 0^{9})$ a, b~(1 \le a, b \le 10^9), $n (0 \leq n \leq 25000)$ n~(0 \le n \le 25000) və $m (0 \leq m \leq 25000)$ m~(0 \le m \le 25000) verilmişdir. Növbəti $n$ sətirdə $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n qiymətləri, sonrakı $m$ sətirdə isə $b_{1}, \dots, b_{m}$ b_1, \ldots, b_m qiymətləri verilmişdir.

Çıxış

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

Nümunələr

Nümunə 1