====== 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})$‎ را بنویسید.‎
===== محدودیت‌ها =====


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

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

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|1‎ \\ 3‎ \\ 1 1‎ \\ 1 2‎ \\ 1 3‎ | 15 |
</WRAP>

<پاسخ>
می‌خواهیم اعداد ‎$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))$‎ قابل حل است و روش آن به صورت زیر است:
  -  یک {{http://en.wikipedia.org/wiki/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))$‎ که در زمان مناسب پاسخ سوال را به‌دست می‌آورد.
</پاسخ>

  * [[سوال ۷۹|سوال بعد]]
  * [[سوال ۷۷|سوال قبل]]