$n$ ماشین در حاشیهی یک سمت خیابان گلبرگ، پشت سر هم پارک شدهاند. یک روز عصر، گلی - کهیکی از ساکنان خیابان گلبرگ است - وارد این خیابان شده و متوجه میشود که جای پارک برای ماشینش وجود ندارد! بهعبارت دقیقتر، اگر فرض کنیم ماشین شماره $i$ (که $1\le i \le n$) از نقطهی $a_i$ (از ابتدای خیابان) تا نقطهی $b_i$ را اشغال کردهاست، طول خیابان $D$ و طول ماشین گلی $L$ است، در این صورت فاصلهی هر دو ماشینی که در خیابان پشت سر هم پارک شدهاند ) و فاصلهی قبل از اولین ماشین در خیابان همگی کمتر از $L$ هستند.
با کمی دقت، گلی در مییابد که بین بعضی از ماشینها فاصله خالی وجود دارد. بهعنوان مثال اگر $[a_1,b_1] = [18,22]$، $[a_2,b_2] = [29,37]$، $[a_3,b_3] = [1,16]$، $[a_4,b_4] = [22,26]$ و طول خیابان $D=37$ باشد، در اینصورت بین ماشین شماره سه و یک، بهاندازهی ۲ واحد فاصلهی خالی (از ۱۶ تا ۱۸) و بین ماشین شماره چهار و دو، ۳ فاصلهی خالی وجود دارد، اما ماشین شمارهیک و چهار بههم چسبیدهاند.
در این حال و هوا، ایدهای که به ذهن گلی میرسد اینست که اگر تعدادی از ماشینها بهسمت جلو یا عقب بروند در اینصورت یک جای خالی مناسب (بهطول حداقل $L$) برای او پیدا میشود. مثلاً در مثال گفته شده در بالا، اگر $L=5$ باشد، کافیست ماشینهای شمارهیک و چهار هر دو، ۳ واحد به سمت جلو حرکت کنند تا بین ماشین شماره سه و ماشین شمارهیک فاصله برابر ۵ ایجاد شده و گلی بتواند ماشینش را پارک کند. واضحست که در برخی مواقع شاید لازم باشد تعداد بیشتری از ماشینها جابهجا شده و از آن میان، عدهای به عقب و عدهای به جلو بروند. ترتیب عقب و جلو رفتن، دلخواه است؛ منتهی ترتیب داخلی ماشینها باید ثابت بماند.
با تجربهی قبلیای که گلی از اهالی خیابان گلبرگ دارد، میداند که برای اینکه ماشین $i$،اُم بهاندازهی $\Delta_i$ واحد حرکت کند، باید به صاحب آن به اندازهی $S_i + \Delta_i \times M_i$ تومان پول بدهد! بهعنوان مثال $S_5 = 100$ و $M_5 = 10$ بدین معنی است که مالک ماشین پنجم، برای اینکه ماشینش تکان بخورد ابتدا ۱۰۰ تومان گرفته و بعد بهازای هر یک واحدی که ماشینش عقب یا جلو برود ۱۰ تومان دیگر هم میگیرد!
در این اوضاع آشفته، گلی از شما کهیک برنامهنویس هستید کمک میخواهد…
برنامهای بنویسید که
| ورودی نمونه | خروجی نمونه |
|---|---|
| 37 5 4 18 22 10 1 29 37 1 10 1 16 0 1 22 26 10 1 | 24 |