C. Сережа ба хоёр дараалал

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сережад бүхэл тоонуудаас бүрдсэн $a_{1}, a_{2}, ..., a_{n}$ ба $b_{1}, b_{2}, ..., b_{m}$ хоёр дараалал байв. Нэг өдөр Сережа уйдсан тул эдгээр хоёр дарааллаар тоглохоор шийдэв. Тоглоомын дүрэм нь маш энгийн байв. Сережа дараах үйл ажиллагаануудын аль нэгийг гүйцэтгэж чадах ба нэг шилжилт, хэд хэдэн шилжилт хийнэ:

  1. $a$ ($a$ эхлээд хоосон биш) дарааллаас хэд хэдэн (хамгийн багадаа нэг) эхний элементүүдийг сонгоно, $b$ ($b$ эхлээд хоосон биш) дарааллаас хэд хэдэн (хамгийн багадаа нэг) эхний элементүүдийг сонгоно; $a$ дарааллын сонгосон элементүүд дундаас хамгийн их индекстэй нь $b$ дарааллын сонгосон элементүүд дундаас хамгийн их индекстэйтэй тэнцүү байх ёстой; Дарааллуудаас сонгосон элементүүдээ устгана.
  2. Хоёр дарааллын бүх элементүүдийг устгана.

Эхний үйл ажиллагаа нь $e$ энергийн нэгжүүдийн үнэтэй ба Сережа электрон дансандаа нэг доллар нэмнэ. Хоёрдугаар үйл ажиллагаа нь энэ үйл ажиллагааг хийхийн өмнөх дарааллын устгасан элементүүдийн тоотой тэнцүү хэмжээний энергийн нэгжийн үнэтэй. Сережа хоёрдугаар үйлдлийг хийсний дараа тэр тоглоомын туршид электрон дансандаа хийсэн бүх мөнгөө авна.

Эхлээд Сережад $s$ энергийн нэгж байсан ба түүний дансанд ямар ч мөнгө байгаагүй. Сережа хамгийн ихдээ хэдэн доллар олж чадах вэ? Анхааруулж хэлэхэд түүний энергийн хэмжээ нь ямар ч үед сөрөг байх ёсгүй.

Оролт

Эхний мөр нь $n$, $m$, $s$, $e$ $(1 ≤ n, m ≤ 10^{5}; 1 ≤ s ≤ 3*10^{5}; 10^{3} ≤ e ≤ 10^{4})$ бүхэл тоонуудыг агуулна. Хоёр дахь мөр нь $n$ ширхэг $a_{1}$, $a_{2}$, $...$, $a_{n}$ $(1 ≤ a_{i} ≤ 10^{5})$ бүхэл тоонуудыг агуулна. Гуравдугаар мөр нь $m$ бүхэл тоонууд $b_{1}$, $b_{2}$, $...$, $b_{m}$ $(1 ≤ b_{i} ≤ 10^{5})$ агуулна.

Гаралт

Сережа хамгийн ихдээ хэдэн доллар олж чадахыг нэг бүхэл тоогоор хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
5 5 100000 1000
1 2 3 4 5
3 2 4 5 1
Гаралт
3
Оролт
3 4 3006 1000
1 2 3
1 2 4 3
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...