ارشیا به شهربازی ال‌دورادو رفته و تصمیم گرفته است فرصت را غنیمت دانسته و از تنها فرصتی که در آن می‌تواند هم بازی کند و هم پول درآورد بهترین استفاده‌ی ممکن را کند!

در این شهربازی تعدادی (نه لزومن متناهی!) دستگاه بازی وجود دارد که هرکدام آن‌ها تعدادی ژتون به عنوان ورودی دریافت می‌نماید و در صورتی که بازیکن بتواند بازی را با موفقیت به پایان برساند مقدار مشخصی طلا به او جایزه می‌دهد. در هنگام ورود به شهربازی تمام دستگاه‌های آن به بازدیدکنندگان معرفی می‌شوند و در اصل بازدیدکنندگان اطلاعات لازم برای بازی کردن هر دستگاه را دارند.

اطلاعات لازم برای هر دستگاه به صورت زیر است:

• دستگاه $i$ ام مقدار $a_i$ ژتون به عنوان ورودی دریافت می‌کند.
• دستگاه $i$ ام به عنوان جایزه $b_i$ کیلو طلا به بازیکن می‌دهد!
• هر دستگاه را می‌توان به هر تعداد دلخواهی بازی کرد و محدودیتی در تعداد استفاده از آن‌ها نیست.

ارشیا با تمام دستگاه‌های موجود در این شهربازی آشنا است و نمی‌خواهد حتی ذره‌ای از سود کردن بگذرد. برای همین نحوه‌ی بردن در هرکدام از دستگاه‌ها را یاد گرفته است و می‌تواند هرکدام از آن‌ها را در صورت شروع کردن با موفقیت به پایان برساند. در نتیجه از شما کمک خواسته تا در بخش‌های مختلف برای حساب کردن بیش‌ترین میزان جایزه‌ی قابل کسب از دستگاه‌های شهربازی به او کمک کنید.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

$1$- الف ($33$ نمره) : فرض کنید تعداد دستگاه‌های شهربازی بی‌نهایت است، و ورودی دستگاه $i$ ام برابر $i$ امین واحد معمول اسکناس‌ها باشد که بصورت اعداد ۱ و ۲ و ۵ ضربدر توان‌های مختلف ۱۰ تولید می‌شود؛ یعنی دنباله‌ی ورودی دستگاه‌ها برابر ۱، ۲، ۵، ۱۰، ۲۰، ۵۰، ۱۰۰، … می‌باشد. همچنین فرض کنید جایزه‌ی دستگاه $i$ برابر $b_i=3^{i-1}$ باشد، اگر ارشیا در ابتدا ۴۱۷۹۶۸۲۲۰۹۸۷۳۰۹۸۴۴۲۹۷۵۲۸۸۴۷۵۲۸۸۵ ژتون داشته باشد، بیش‌ترین جایزه‌ی قابل کسب توسط او برابر چند کیلو طلا به پیمانه‌ی $\Delta$ است؟

$1$- ب ($33$ نمره) : فرض کنید تعداد دستگاه‌های شهربازی بی‌نهایت، ورودی دستگاه $i$ ام برابر $a_i=i$ و جایزه‌ی آن برابر $b_i=(i\oplus(i-1))$ باشد، اگر ارشیا در ابتدا ۹۱۶۷۱۵۳۴۰۱۳۰۷۲۲۵۹۰۱ ژتون داشته باشد، بیش‌ترین جایزه‌ی قابل کسب توسط او برابر چند کیلو طلا به پیمانه‌ی $\Delta$ است؟

$1$- ج ($34$ نمره) : فرض کنید تعداد دستگاه‌های شهربازی برابر $n=10^5$، ورودی دستگاه $i$ ام برابر $a_i=2^{i-1}$ و جایزه‌ی آن برابر $b_i$ باشد $(b_i\leq5\times10^5)$، اگر ارشیا در ابتدا $k$ ژتون داشته باشد ($k$ یک عدد $10^6$ رقمی است)، بیش‌ترین جایزه‌ی قابل کسب توسط او برابر چند کیلو طلا به پیمانه‌ی $\Delta$ است؟ (داخل فایل items.txt در خط اول ورودی عدد $k$ و در خط دوم ورودی مقادیر آرایه‌ی $b$ به ترتیب داده شده‌اند)