C. Цаг унших

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

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

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

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

Галзуу эрдэмтэн Майк удаан хатуу дискүүдийг ашигладаггүй. Түүний "хард драйв"-ын сайжируулалт нь ганц бус $n$ ширхэг зэрэгцээгээр өгөгдлийг уншиж чадах ялгаатай толгойноос бүтсэн байна.

Гаднаас нь ажих аваас Майкын "хард драйв" нь замуудын төгсгөлгүй массив болж байв. Массивын замууд нь зүүнээс баруунтаа $1$-ээс эхлэсэн тоогоор дугаарлагдсан болно. Анхны төлөвт $i$ дахь уншигдаж буй толгойн дээр $h_i$ замын дугаар байрлана. Уншигдаж буй толгойнууд тус бүрд "хард драйв"-ын микропрограм зүүн болон баруун талын ганц зам руу хөдлөх боломжтой, эсвэл одоо байгаа зам дээр орхидог. Ажиллагааны явцад толгой бүрийн хөдөлгөөн нь өөрсдийн хамаатай дарааллаа өөрчилж чадах бусад толгойн хөдөлгөөнтэй харшилдахгүй ба энд аль ч замуудын дээр олон ширхэг уншигдаж буй толгой байх боломжтой. Хэрэв багадаа ганц ширхэг толгой тухайн замаар явсан бол тухайн замыг уншсан гэж үзнэ. Тухайлбал $h_1, h_2, ..., h_n$-аар дугаарлагдсан бүх зам ажиллагааны эхэнд уншигдсан.

Майк $m$ ширхэг ялгаатай замууд болох $p_1, p_2, ..., p_m$ тоонуудыг унших хэрэгтэй. Микропрограмын толгойг хөдөлгөж өгөгдсөн замуудыг бүгдийг нь уншихад шаардагдах хамгийн бага хугацааг олно уу. Мөн дурын бусад замууд уншигдсан байж болно.

Оролт

Оролтын эхний мөрөнд дискний толгойн тоонууд болон унших ёстой замуудыг тоог илэрхийлэх $n$, $m$ ($1 ≤ n, m ≤ 10^5$) тоонууд зайгаар тусгаарлагдан өгөгдөнө. Хоёр дахь мөрөнд толгойн байрлалуудыг илэрхийлэх $n$ ширхэг ялгаатай тоо болох $h_i$ ($1 ≤ h_i ≤ 10^{10}$, $h_i < h_i + 1$) өсөх дарааллаар өгөгдөнө. Гурав дахь мөрөнд унших замуудын тоог илэрхийл $m$ ширхэг ялгаатай тоо болох $p_i$ ($1 ≤ p_i ≤ 10^{10}$, $p_i < p_i + 1$) өсөх дарааллаар өгөгдөнө.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Бүх хэрэгтэй замыг унших хамгийн бага хугацааг секундаар илэрхийлэх ганц тоог хэвлэ.

Орчуулсан: Э.Шүрэнчулуун

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

Оролт
3 4
2 5 6
1 3 6 8
Гаралт
2
Оролт
3 3
1 2 3
1 2 3
Гаралт
0
Оролт
1 2
165
142 200
Гаралт
81

Тэмдэглэл

The first test coincides with the figure. In this case the given tracks can be read in 2 seconds in the following way:

  1. during the first second move the 1-st head to the left and let it stay there;
  2. move the second head to the left twice;
  3. move the third head to the right twice (note that the 6-th track has already been read at the beginning).

One cannot read the tracks in 1 second as the 3-rd head is at distance 2 from the 8-th track.

Сэтгэгдлүүдийг ачааллаж байна...