TopCoder

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

50.0% (13/26)

Tags

Description

「每個人兩腿之間都有一個異次元新世界。」某個最後死於直腸出血的人曾這麼說過。

修羅少年在失去了魔獸世界之後,決定開發自己潛在的異次元世界,於是他上了某個知名網站,觀摩其他前輩進行異次元突破的過程。

「看起來好痛!我愛台灣!」

沒吃過苦的修羅少年,這時打開了「股溝控」(某知名瀏覽器),連上「股溝」(某知名搜尋引擎),在搜尋列打了「無痛異次元突破」的字樣開始搜尋。

他發現無痛異次元突破是不可能的,可是他找到了一篇學術研究,上面寫著:
「所謂異次元突破,就是使用一個厚壁空心圓柱的工具(亦即外圈跟內圈是同心圓,兩圈之間是實心的),將圓柱圓心對準異次元邊界的中心捅下去的過程。異次元突破是每個男人必經的過程,基於人怕痛的心理,自然希望突破造成的疼痛愈少愈好,但經過英國研究證明,疼痛是不可能降低的。每個人異次元的邊界上會有很多關鍵點,每個關鍵點被捅到時會產生不同的爽度(當然也有負的),爽度是可以覆蓋掉疼痛的。藉此可以間接減輕疼痛。」
修羅少年想請你幫他找出最爽可以多爽。

Input Format

第一行有一個整數N,表示有多少關鍵點。

接下來有N行,每行有三個數字Xi, Yi, Ki,用來描述第i個關鍵點。

(Xi, Yi)表示第i個關鍵點的位置、Ki表示該關鍵點被捅到的爽度。

-1,000,000,000 <= Xi, Yi <= 1,000,000,000
-10,000 <= Ki <= 10,000

另外,異次元邊界的中心永遠在(0, 0)

Output Format

輸出一個整數代表最大爽度。

Sample Input

6
1 0 1
0 2 3
-3 0 -5
0 -4 5
5 0 4
0 6 -10

Sample Output

9

Hints

對於50%測資,N <= 1,000
對於70%測資,N <= 10,000
對於100%測資,N <= 100,000

(範例測資中,外圈半徑 = 5, 內圈半徑 = 4)

Problem Source

原TIOJ1638 / Problem Setter: ATP
Description By DarkBtf
Special Thanks: yuscvscv

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144