Masala #0339

Bitboy kunlardan bir kun omadli yo’laklar lotoreyasida g’olib bo’ldi va u qancha miqdorda sovrin sohibi bo’lishi o’ziga bog’liq bo’lib qoldi. Sovrin miqdori quyidagi shaklda aniqlanadi:

• Bitboyga ikkita A va B yo’lak beriladi, har bir yo’lakning uzunligi N ga teng va ikkala yo’lakning ham har bir birligida bittadan son yozilgan, bu son Bitboy shu raqamni bosganida unga shu summa miqdorida sovrin qo’shilishini anglatadi;
• Bitboy yo’lakdan hech qachon ortga burilmaydi, har qadamda i-pozitsiyadan i+1 – pozitsiyaga siljiydi;
• Bitboy bir yo’lakdan boshqasiga o’tish uchun X jarima to’lashi kerak bo’ladi;
• Bitboy dastlab yurishni ixtiyoriy yo’lakdan boshlashi, oxirida ixtiyoriy yo’lakda to’xtatishi mumkin;
• Qolgan ma’lumotlarni izohdan bilib olishingiz mumkin.

Kirish faylining dastlabki satrida ikkita butun son, N(1 ≤ N ≤ 10⁵) va X(0 ≤ X ≤ 10⁹) sonlari kiritiladi.

Ikkinchi satrda N ta butun son, A(0 < A_i ≤ 10⁹) birinchi yo’lakdagi sonlar ketma-ketligi kiritiladi.

Uchinchi satrda N ta butun son, B(0 < B_i ≤ 10⁹) ikkinchi yo’lakdagi sonlar ketma-ketligi kiritiladi.

Chiqish faylida yagona son, Bitboyning maksimum sovrin miqdorini aniqlang!