انجام دادن تکالیف معمولاً موجب می‌شود دانش‌آموزان درک عمیق‌تری نسبت به درس داشته باشند. هری پاتر به عنوان یکی از دانش‌آموزان هاگوارتز، خیلی وقت‌ها تکالیف زیادی را باید انجام دهد. او هر روز، به عنوان تکلیف، یک مجموعه مسئله از استادانش می‌گیرد. مسئله‌ی $i$ به اندازه‌ی $t_i$ زمان لازم دارد تا کامل انجام شود. با فرض داشتن یک برنامه (یا به عبارت دیگر یک ترتیب از مسئله‌ها)، هر مسئله‌ی $i$ یک «زمان پایان»ای دارد که آن را با $C_i$ نمایش می‌دهیم. برای مثال اگر مسئله‌ی $j$ اولین مسئله‌ای باشد که حل می‌شود آنگاه زمان پایان آن برابر $C_j=t_j$ است. هر مسئله‌ی $i$ همچنین یک «وزن» مشخص‌شده‌ی $W_i$ دارد که اهمیت آن مسئله را در ایجاد تسلط بر دانش مربوطه نشان می‌هد. هری می‌خواهد مسئله‌هایش را طوری مرتب کند که جمع وزن‌دار زمان پایان مسئله‌ها یعنی $W_1\times C_1+W_2 \times C_2+\ldots +W_n\times C_n$ کمینه شود. برنامه‌ای بنویسید که با گرفتن مجموعه‌ای از $n$ مسئله و هزینه‌ی زمانی هرمسئله ($t_i$) و وزنش ($W_i$) کمترین مقدار ممکن را برای جمع وزن‌دار زمان پایان‌ها یعنی $$ \sum_{i=1}^{n} W_i*C_i $$ پیدا کند. برای مثال فرض کنید دو مسئله داریم: مسئله‌ی اول به اندازه‌ی $t_1=2$ زمان می‌برد و وزن آن $w_1=12$ است و مسئله‌ی دوم به اندازه‌ی $t_2=3$ زمان می‌برد و وزن آن $w_2=4$ است. در این صورت، اگر مسئله‌ی اول ابتدا حل شود مجموع وزن‌دار زمان‌ها $12 \times 2+4 \times 5=44$ می‌شود و اگر مسئله‌ی دوم ابتدا حل شود، مجموع وزن‌دار برابر $4 \times 3+12 \times 5=72$ می‌شود که به وضوح کمترین مقدار مجموع وزن‌دار زمان‌ها برابر $44$ است. # محدودیت‌ها $$ 1 \leq n \leq 20000 $$ $$ 1 \leq t_i, W_i, \leq 10000 $$ + زبان C و C++ + محدودیت زمان: ۵۰۰ میلی‌ثانیه + محدودیت حافظه: ۱۵۰ مگابایت + زبان پایتون و جاوا + محدودیت زمان: ۱۲۵۰ میلی‌ثانیه + محدودیت حافظه: ۲۰۰ مگابایت # ورودی در خط اول ورودی $n$ آمده است که تعداد مسئله‌ها را نشان می‌دهد. در هر یک از $n$ خط بعد دو عدد $t_i$ و $W_i$ که به ترتیب زمان حل شدن و وزن مسئله است آمده است. # خروجی در تنها سطر خروجی فقط یک عدد صحیح بنویسید که نشان‌دهنده‌ی کمترین مقدار ممکن برای مجموع وزن‌دار زمان پایان‌ها مسئله‌ها باشد. # مثال ## نمونه ورودی ``` 2 2 12 3 4 ``` ## نمونه خروجی ``` 44 ```