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

Өнөөдөр Жэфф цаасан дээр $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)$.

Гаралт

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

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