1719 測資加強 已 rejudge
1648 . 廣告看板配置
Description
你是一家名為Ad-M@S廣告公司的員工之一，這家廣告公司的業務是專門幫人在特定的公共場所製作並架設各式各樣廣告看板。
其中，主要的種類分為橫掛在空中的招牌和立在地上的看牌。
現在，由於暑假的到來，許多服飾、精品、旅遊等等業者都想要藉此機會做個廣告以利宣傳和推銷商品。
也因為這個緣故，Ad-M@S公司接收到了許多客戶製作並架設廣告看板的請求，但由於位置有限，
同時擺設許多廣告看板將會有互相遮擋的問題，而這樣將會影響廣告看板的宣傳效果，所以實在不能答應所有客戶的需求。
而為了幫公司取得最大的利益，在已經知道每個客戶要求的廣告看板位置座標、涵蓋的範圍以及願意支付的酬勞金額之下，
你想要在這些客戶要求中選擇一些客戶，使得他們要求擺設的廣告看板位置兩兩不會衝突，且收益的總和最大。
為了簡化問題，我們不考慮廣告看板的厚度、觀看的角度，並且假設所有的廣告看板都必須是矩形。
並且保證所有的廣告看板至少會有一條邊貼著直線 X = 0（橫掛的招牌）或 Y = 0（地上的立牌）。
Figure 1. 即範例輸入的內容，答案為選標記粗框的三個矩形，S = 5 + 5 + 2。
兩廣告看板互相遮擋到若且為若它們交集的面積大於 0 。
Input Format
本題輸入的測試檔只有單筆測試資料，第一行有且僅有一個整數 N，代表有 N 個客戶提出要求。
接下來有N行，其中的第 i 行會給出第 i 個客戶提出的要求內容，包括五個整數 Xi1, Yi1, Xi2, Yi2 和 Ri，
代表廣告看板的左上角座標 (Xi1, Yi1)、右下角座標 (Xi2, Yi2)，以及製作並擺設這個廣告看板的酬勞。
對於所有測試資料，保證1 ≤ N ≤ 1000，0 ≤ Xi1 < Xi2 ≤ 108，0 ≤ Yi2< Yi1 ≤ 108，0 ≤ Ri ≤ 108，∀ 1 ≤ i ≤ N。
Output Format
請輸出一個整數 S，代表可以獲得的最大收益。
Sample Input 1
5
2 2 6 0 5
3 5 5 0 4
0 8 1 6 1
7 3 8 0 2
0 7 4 4 5
2 2 6 0 5
3 5 5 0 4
0 8 1 6 1
7 3 8 0 2
0 7 4 4 5
Sample Output 1
12
Hints
Problem Source
原TIOJ1648 / Skyly & Shik Contest II (Problem I)
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 |