- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
انجام دادن تکالیف معمولاً موجب میشود دانشآموزان درک عمیقتری نسبت به درس داشته باشند. هری پاتر به عنوان یکی از دانشآموزان هاگوارتز، خیلی وقتها تکالیف زیادی را باید انجام دهد. او هر روز، به عنوان تکلیف، یک مجموعه مسئله از استادانش میگیرد. مسئلهی \(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 \times 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\) است.
ورودی
در خط اول ورودی \(n\) آمده است که تعداد مسئلهها را نشان میدهد. در هر یک از \(n\) خط بعد دو عدد \(t_i\) و \(W_i\) که به ترتیب زمان حل شدن و وزن مسئله است آمده است.
\[1 \leq n \leq 20000 \] \[1 \leq t_i, W_i, \leq 10000\]
خروجی
در تنها سطر خروجی فقط یک عدد صحیح بنویسید که نشاندهندهی کمترین مقدار ممکن برای مجموع وزندار زمان پایانها مسئلهها باشد.
مثال
ورودی نمونه ۱
2
2 12
3 4
خروجی نمونه ۱
44