TopCoder

User's AC Ratio

80.0% (8/10)

Submission's AC Ratio

32.6% (14/43)

Tags

Description

「想要我的財寶嗎?想要的話自己去尋找吧!我把所有的財寶都藏在那裡了。」  

                                   ----海賊王 哥爾‧D‧羅傑

在偉大的航道航行多時,也經歷了許多的風風雨雨的草帽小子海賊團。
這次到達了一個叫做「羅莉島」的島嶼,島上住著許多的小羅莉,然而他們卻對於一位叫魔人姜姜的邪惡魔王深感頭痛。因為他的行蹤捉摸不定,往往突然從趁人不備時,襲擊路上的落單的小羅莉。魯夫一行人,為了幫助廚師香吉士拯救整座島上的小羅莉們(以便往後繼續吃好吃的美食),所以前往魔人姜姜的巢穴準備跟他決一死戰。

經過了一番的探索追尋,終於來到了魔人姜姜的巢穴,這時發現魔人姜姜竟然在......。憤怒的魯夫一行人馬上和魔人姜姜進行決鬥。

但是因為魔人姜姜實在是太邪惡了,竟然利用抓來的小羅莉當作人質,但是頭腦簡單的魯夫沒想那麼多,所以很快速的將魔人姜姜給打飛了。

但是更危險的還在後頭,因為小羅莉身上都被魔人姜姜裝了定時炸彈,到一定的時間就會爆炸,不知道該如何解除的魯夫開始感到緊張與焦急...。

好在聰明的娜美早就發現這種情形,他已經先把每個羅莉身上的炸彈爆炸時間都預測出來了。
再加上騙人布對炸藥的認識,也將魯夫破壞每個羅莉身上的炸藥時間都算準了。

現在魯夫必須將每顆炸彈都破壞掉,以便能繼續吃到美食....阿不,是拯救小羅莉。

不過因為時間緊迫,所以有些炸藥魯夫必須要進入二檔來減少破壞時間,但是因為剛剛和魔人姜姜決鬥,所以HP已經耗費許多,假如他二檔使用太久的話也會為害到他的生命,所以當他破壞完一顆炸彈時就會恢復一般狀態。
當然不需要對於每顆炸彈都進入二檔,因為有些是有充足時間慢慢破壞的。

假設他用x%的力氣進入的二檔時,破壞某顆炸藥的時間會縮短x%,相對的HP也會減少x。(x代表某個非負實數)
當然假如他完全進入二檔時(100%),瞬間就可以將炸藥破壞掉。

身為剛好路過一位程式設計師。你決定幫他們拯救小羅莉,現在你的任務就是要計算最少魯夫會減少多少HP。

Input Format

第一行包含一數n(0<=n<=500000)代表被裝上炸藥的小羅莉。
接下來n行每行包含兩個非負實數w_i,t_i(0<=w_i,t_i<=109),w_i代表破壞第i顆炸彈所需的時間,t_i則代表第i顆炸彈爆炸的時間。

Output Format

輸出一數X(至小數後三位)代表魯夫至少要減多少HP,才能將小羅莉全部救出。

Sample Input 1

1
5.0 4.0

Sample Output 1

20.000

Hints

Problem Source

原TIOJ1529 / INFOR 22nd幹部考(prob F)。

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6
6 1500 65536 262144 7
7 1500 65536 262144 8
8 1500 65536 262144 9
9 1500 65536 262144 10