Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
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$.