آقا داوود در یک خیابان طویل، مشغول آماده‌سازی یک تمرین سخت فکری-قدرتی برای شاگردانش است. می‌دانیم اگر خیابان را به صورت یک محور مختصات در نظر بگیریم در هر نقطه‌ی با مختصات طبیعی آن، یک بشکه سیمان که در ابتدا خالی است قرار دارد. حال آقا داوود برای پر کردن بشکه‌ها $Q$ بار عملیات زیر را تکرار می‌کند:

1. سه عدد طبیعی $S$ و $V$ و $C$ به صورت دلخواهی انتخاب می‌کند.
2. حال یک منبع سیمان با حجم $V$ را پر از سیمان کرده و همراه با یک پیمانه به حجم $C$، به مکان بشکه‌ی $S$-ام خیابان می‌رود.
3. حال به این صورت عمل می‌کند که اگر سیمان‌های داخل منبع حجمی کمتر از $C$ داشت، تمام سیمان آنرا در بشکه‌ای که در مکان آن قرار دارد می‌ریزد، و به کل فرآیند خاتمه می‌دهد، در غیر این صورت با استفاده از پیمانه‌ای که دارد، $C$ واحد از سیمان‌های منبع را در بشکه می‌ریزد و سپس به بشکهی بعدی می‌رود و باز عملیات 3 را تکرار می‌کند. (منظور از بشکه‌ی بعدی برای بشکه‌ای که در مکان $X$ قرار دارد، بشکه ایست که در مکان $X+1$ قرار دارد).

حال آقا داوود کارهایش را انجام داده و نویت تمرین فرا رسیده است. تمرین به این صورت است که یک شاگرد برای انجام تمرین، باید دو عدد طبیعی $B$ و $L$ انتخاب کند و سپس با یک پیمانه به حجم $L$ به مکان بشکه $B$-ام خیابان برود. حال اگر بشکه‌ای که در کنارش قرار داشت سیمانی با حجم کمتر از $L$ واحد داشت او به تمرینش پایان می‌دهد، در غیر است صورت با استفاده از پیمانه‌ای که دارد، $L$ واحد سیمان از بشکه خارج و به بیرون می‌ریزد و به سمت بشکه‌ی بعدی می‌رود و همین عمیات را تکرار می‌کند. حال شما باید بیشترین سیمانی که یک نفر به این صورت می‌تواند روی زمین بریزد را در خروجی چاپ کنید.

• سطر اول ورودی شامل عدد طبیعی $1\leq Q \leq 10^6$، تعداد عملیاتهای پرکردن بشکه‌های سیمان، است.
• سطرهای دوم تا $Q+1$-ام بیانگر ویژگی‌های عملیات‌های آقا داوود است به طوری که سطر $i+1$-ام ورودی که $1\leq Q \leq i$ به ترتیب شامل سه عدد طبیعی، $1\leq s_i \leq 10^9$، بشکه‌ی شروع عملیات $i$-ام، $1\leq v_i \leq 10^9$، ظرفیت حجمی مخزن در عملیات $i$-ام و $1\leq c_i \leq 10^9$، ظرفیت حجمی پیمانه در عملیات $i$-ام، است.
• در ۲۰ درصد از ورودی‌ها، تمامی اعداد ورودی‌ کوچکتر مساوی $3^{10}$ هستند.
• در ۵۰ درصد از ورودی‌ها، تمامی اعداد ورودی کوجکتر مساوی $6^{10}$ هستند

در تنها سطر خروجی بیشترین میزان سیمانی که می‌توان به بیرون از بشکه‌ها ریخت را چاپ کنید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

در ورودی اول بشکه‌های 1 تا 4 دارای به ترتیب دارای حجم‌های 1، 2، 3 و 4 هستند و سایر بشکه‌ها خالی هستند. به ازای $B=2$ و $L=2$ یا $B=3$ و $L=3$ می‌توان 6 واحد سیمان روی زمین ریخت. در ورودی دوم بشکه‌های 1 تا 5 به ترتیب دارای حجم‌های 3، 2، 2، 2 و 1 هستند و سایر بشکه‌ها خالی هستند. به ازای $B=1$ و $L=2$ می‌توان 8 واحد سیمان روی زمین ریخت. در صورتی که $B=1$ و $L=1$ 5 واحد سیمان و در صورتی که $B=1$ و $L=3$ 3 واحد سیمان بر روی زمین می‌ریزد.

• سوال بعد