Masala D

Davron shahrida har yilgi Domino festivali bo‘lib o‘tmoqda. Festivalda shahar markazida joylashgan maxsus domino maydoni mavjud. Bu maydon N qator va aynan 3 ustundan iborat. Har bir katakda festival tashkilotchilari tomonidan turli xil qiymatli ballar yozilgan.

Mirjalol ushbu festivalda ishtirok etmoqda va uning ixtiyorida aynan K dona domino mavjud. Har bir domino o‘lchami 2x1 bo‘lib, Mirjalol ularni xohlagancha burib yoki aylantirib joylashtirishi mumkin. Uning maqsadi, domino kataklari bilan qoplagan maydonidagi sonlar yig‘indisini imkon qadar maksimal qilishdir.

Mirjalolga aynan K ta dominodan foydalanib, hech qanday bir-birini ustiga chiqmagan holda, maksimal ballarni yig‘ishga yordam bering!

Birinchi qatorda ikkita butun son \(N(1\le N\le 10^3)\) – maydonning qatorlari soni va \(K(1\le K\le 10^3)\) – domino toshlari soni beriladi. Keyingi N ta qatorda uchtadan butun son yozilgan bo‘ladi. Bu sonlar maydonning tegishli kataklaridagi ballarni ifodalaydi. Har bir sonning absolyut qiymati \(10^6\) dan kichik bo‘ladi.

Bitta son chiqariladi – aynan \(K\) ta dominodan foydalanib olinishi mumkin bo‘lgan maksimal ballar yig‘indisi.