C. Жэфф ба Хаалт

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

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

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

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

Жэффт зөв хаалтнуудын дараалал таалагддаг.

Өнөөдөр Жэфф цаасан дээр $nm$ хаалтнаас тогтох хаалтнуудын зөв дараалал бичих гэж байна. Энэ дарааллын хаалтуудыг зүүнээс баруун руу нь $0$-с $nm-1$ хүртэл дугаарлая. $i$ дэх хаалт "нээх" хаалт бол $a_{i modn}$ литр бэх зарцуулагдах ба "хаах" хаалт бол $b_{i modn}$ литр бэх зарцуулна.

Танд $a,b$ дарааллууд, мөн $n,m$ тоонуду өгөгдөнө. Жэфф $nm$ урттай зөв хаалтны дараалал бичихийн тулд хамгийн багадаа ямар хэмжээний бэх шаардагдах вэ?

$x$ тоог $y$ тоонд хуваахад гарах үлдэгдлийг $x mod y$ гэж тэмдэглэдэг.

Оролт

Эхний мөрөнд $n , m (1\le n\le 20; 1\le m\le 10^7; m$ нь тэгш $)$ бүхэл тоонууд өгөгдөнө. Дараагийн мөрөнд $n$ ширхэг бүхэл тоонууд өгөгдөнө $ a_0, a_1, ..., a_{n-1} (1\le a_i\le 10)$. Дараагийн мөрөнд мөн $n$ ширхэг бүхэл тоонууд өгөгдөнө $ b_0, b_1, ..., b_{n-1} (1\le b_i\le 10)$.

Гаралт

Хамгийн багадаа хэдэн литр бэх хэрэглэхийг илэрхийлэх тоон утгыг хэвлэ.

Орчуулсан: Төрбат

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

Оролт
2 6
1 2
2 1
Гаралт
12
Оролт
1 10000000
2
3
Гаралт
25000000

Тэмдэглэл

In the first test the optimal sequence is: $()()()()()()$, the required number of ink liters is $12$.

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