Numbers

فرض کنید $f(x)$ برابر باشد با کوچک‌ترین $k$ به طوری که $\lfloor\frac{x}{2^k}\rfloor = 0$. به شما $n$ عدد $a_1$ تا $a_n$ داده شده است. شما باید $n$ عدد صحیح بزرگ‌تر از صفر $b_1$ تا $b_n$ را بیابید به طوری که :

به ازای هر $i$ و $j$ ($i \neq j$) هیچ $k \geq 0$ای وجود نداشته باشد بهطوری‌که $\lfloor\frac{b_i}{2^k}\rfloor = b_j$.
$\sum_{i=1}^{n}a_i \times f({b_i})$ کمینه باشد.

ورودی

در سطر اول ورودی، عدد $1 \leq m \leq 10^5$ آمده است.
در $m$ سطر بعد، در سطر $i$ام دو عدد $1 \leq x_i \leq 10^5$ و $1 \leq y_i \leq 10^5$ آمده است که نشان می‌دهد تمامی اعداد $a_{\sum_{j=1}^{i-1}x_j + 1}$ تا $a_{\sum_{j=1}^{i-1}x_j + x_i}$ برابر با $y_i$اند.
$n$ برابر است با .$\sum_{i=1}^{m} x_i$

خروجی

در تنها سطر خروجی مقدار$\sum_{i=1}^{n}a_i \times f({b_i})$ را بنویسید.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه	خروجی نمونه
1 3 1 1 1 2 1 3	15

پاسخ

می‌خواهیم اعداد $b_1$ تا $b_n$ را طوری به‌دست بیاوریم که شرایط سوال را برقرار کند. فرض کنید $c_1$ تا $c_n$ به ترتیب رشته‌های از صفر و یک باشند و $c_i$ برابر باشد با نمایش $b_i$ در مبنای دو که‌یک اول آن حذف شده است. در این صورت مسئله به سوال معروف زیر تبدیل می‌شود:

می خواهیم $n$ رشته $c_1$ تا $c_n$ را طوری پیدا کنیم که هیچ رشته‌ای رشته دیگر نباشد و مجموع ضرب $a_i$ در طول $c_i$ کمینه شود.

این مسئله با استفاده از الگوریتم huffman coding در زمان ${\cal O} (n log(n))$ قابل حل است و روش آن به صورت زیر است:

یک Multiset از $a_i$ ها درست کن.
مقدار $x$ را برابر با صفر قرار بده.
تا زمانی که تعداد اعداد multiset ای یک بیش‌تر است کار زیر را انجام بده:

$a$ را برابر کم‌ترین عدد multiset قرار بده و آن را از multiset حذف کن.
$b$ را برابر کم‌ترین عدد multiset قرار بده و آن را از multiset حذف کن.
مقدار $x$ را با $a+b$ جمع کن و $a+b$ را در multiset قرار بده.

مقدار $x$ که از الگوریتم بالا به‌دست می‌آید، همان جوابیست که باید در خروجی چاپ شود. مقدار $n$ زیاد است و انجام تمامی عملیات بالا در زمان مناسب امکان‌پذیر نیست. فرض کنید در یک مرحله از کار کم‌ترین عدد multiset $a$ باشد و تعداد $a$های multiset برابر با $c$ باشد، در این صورت ما یک کار ثابت را $\frac{c}{2}$ بار انجام می‌دهیم، که با پیاده‌سازی درست می‌توان هر کدام از این کارها را یک بار انجام داد. در این صورت پیچیدگی زمانی برنامه‌ما برابر خواهد بود با ${\cal O}(m \times log(m))$ که در زمان مناسب پاسخ سوال را به‌دست می‌آورد.