The 4th Shinobi War

Batas Waktu	 1s
Batas Memori	 32 MB
Deskripsi

Di dalam dunia shinobi, negara-negara terbagi menjadi desa-desa. Desa-desa tersebut dilindungi dan dijaga oleh pasukan-pasukan ninja yang terkenal kuat.

Adalah desa konohagakure yang menjadi pencetus dan pemimpin liga shinobi. Selama bertahun-tahun liga tersebut telah berhasil menjaga kedamaian di dunia shinobi setelah perang shinobi ketiga dimana Obito berhasil mengubah bulan menjadi mangekyou sharingan, namun justru dirinya sendiri yang jatuh ke dalam genjutsu-nya (?). Yah... Selama bertahun-tahun konoha hidup dalam kedamaian. Namun, semuanya berubah ketika negara api menyerang. (Loh!!? Bukannya konoha berada di dalam negara api?)

Musuh bergerak dengan sangat cepat, hingga dalam beberapa hari, mereka akan tiba di perbatasan desa. Warga desa yang mengetahui hal ini menjadi ketakutan. Kerusuhan terjadi dimana-mana, belum lagi kenaikan harga ramen yang dipicu kenaikan harga BBM belakangan ini turut membuat warga desa marah.

Naruto, yang saat itu sudah menjadi hokage ke-sembilan, memerintahkan untuk mengevakuasi semua warga konoha. Karena mengevakuasi semua warga membutuhkan waktu, maka Naruto mengirimkan dua anbu (ninja elite) untuk menghambat gerakan musuh. Ternyata, di jalan menuju konoha sudah disiapkan beberapa jebakan yang dipersiapkan untuk perang shinobi ke-tujuh (The 7th Shinobi War).

Kedua anbu tersebut, yang adalah Hashirama Uchiha dan Madara Senju mempelajari cara kerja perangkap tersebut. Ternyata ada dua baris perangkap, satu akan dilewati Hashirama dan satu akan dilewati oleh Madara. Setiap perangkap memiliki ‘nilai kekacauan’, semakin tinggi nilainya, maka perangkap tersebut bila diaktifkan akan semakin meperlambat pergerakan musuh. Anggap nilai-nilai kekacauan perangkap yang dilewati hashirama adalah j1 , j2 , ... , jN , sedangkan yang dilewati oleh Madara adalah k1 , k2 , ... , kN (perangka nomor 1 adalah perangkap paling kiri dan perangkap ke-N adalah perangkap paling kanan). Perangkap itu bekerja bila Hashirama dan Madara mengaktifkan salah satu perangkap secara bersamaan, dan akan menyebabkan kekacauan sebesar ( ji x kl ) dengan ji adalah perangkap yang diaktifkan Hashirama dan kl adalah perangkap yang diaktifkan Madara. Setiap perangkap hanya boleh diaktifkan sekali.

Dengan jurus mata sakti klan Uchiha yaitu ‘Byakugan’. Hashirama dapat mengetahui nilai kekacauan dari setiap perangkap. Satu hal lagi, Hashirama dan Madara adalah dua petarung legendaris Konoha yang telah melindungi Konoha dalam Perang Shinobi Ke-Lima (The 5th Shinoby War). Sehingga mereka tidak akan kembali ke perangkap yang pernah mereka lewati. Mereka mulai dari perangkap yang paling kiri (nomor 1), dan terus bergerak ke kanan. Untuk setiap perangkap, mereka boleh memilih untuk mengaktifkannya atau melewatinya, indeks perangkap yang diaktifkan  oleh keduanya tidak harus sama (artinya, bila hashirama mengaktifkan perangkap ke-2, madara bisa saja mengaktifkan perangkap ke-5). Sebagai petarung legendaris, mereka lebih baik mati daipada kembali ke perangkap yang pernah diinjaknya (lebaipol~).

Karena terus bertengkar mengenai strategi pengaktifan perangkap, akhirnya mereka memutuskan bertanya kepada Naruto selaku hokage untuk menentukan perangkap mana saja yang diaktifkan. Karena tidak begitu pintar (yah, dia memang bodoh semenjak di akademi ninja) dia tidak bisa menentukan langkah optimal. Maka dia meminta bantuan anda selaku peserta ujian chuunin yang sedang terjebak di area musuh karena invasi negara api untuk menyelesaikan masalah ini. (Sudah terjebak, diminta bantuan lagi, dasar Naruto!).

Format Masukan

Baris Pertama berisi satu bilangan N. baris kedua berisi N bilangan, barisan perangkap yang akan dilewati Hashirama. Baris ketiga berisi N bilangan, barisan perangkap yang akan dilewati madara.

Format Keluaran

Satu angka, jumlah kekacauan maksimal yang bisa disebabkan.

Contoh Masukan

5
5 1 1 3 0
4 2 3 5 9
Contoh Keluaran

55
Penjelasan

Pada awalnya, Hashirama dan Madara mengaktifkan perangkat pertama, menghasilkan 4 X 5 = 20 kekacauan. Lalu Hashirama maju ke perangkap kedua, sedangkan Madara bergerak ke perangkap ketiga menghasilkan 1 X 3 = 3 kekacauan. Selanjutnya, Hashirama berada di perangkap ketiga dan Madara di perangkap keempat menghasilkan 1 X 5 = 5 kekacauan. Terakhir Hashirama berada di perangkap keempat dan Madara berada di perangkap kelima menghasilkan 3 X 9 = 27 kekacauan. Jadi totalnya 20 + 3 + 5 + 27 = 55 kekacauan.

Subtask

Subtask 1 (nilai 20) : 1 ≤ N ≤ 8

Subtask 2 (nilai 40) : 1 ≤ N ≤ 80

Subtask 3 (nilai 40) : 1 ≤ N ≤ 1.000

Semua bilangan pada input adalah bilangan non-negatif yang tidak melebihi 1.000.000

Peringatan

Karena pada komik yang sudah dikeluarkan, Eichiro Oda baru menulis komik seri Naruto hanya sampai Perang Shinobi ke-Tiga (The 3rd Shinobi War). Maka peserta yang telah membaca soal ini DILARANG KERAS membocorkan cerita ini berhubungan penulis soal mendapatkan kisah kelanjutan seri Naruto ini dari sumber yang terpercaya!