1933 . 巨無霸冰淇淋
TopCoder
Tags
Description
為了增進觀光收益，TOI市的市長計畫在市中心建造了一支「巨無霸冰淇淋」。這支冰淇淋不但很大，完全融化所需時間也異常的長，可以在$L$秒內維持基本的形狀。
除了增加觀光收入外，TOI市市長也想藉由這個機會建立良好外交形象。因此，他邀請$N$位政界大老以及其它市的市長前往參觀。然而收到的回應實在是太熱烈，$N$個人所提出的參觀行程有許多重複之處，因此TOI市市長想找出一個最能提升TOI市外交形象的方案。
具體而言，TOI市市長每次接待一個人（以下簡稱為甲）的時候都需要從甲的所在地開始接待他到市中心的巨無霸冰淇淋為止。甲的出發時間$x_i$（代表在冰淇淋建造完成後$x_i$秒）和旅程所需時間$t_i$（秒）是確定的，而在這段時間TOI市市長理所當然地無法接待其它人。為了簡化問題，假設市長從巨無霸冰淇淋移動到被接待人的所在地不用消耗時間，也就是說在$x_i+t_i$時刻TOI市市長可以馬上開始下一個接待行程。
雖然巨無霸冰淇淋在$L$秒內可以保持基本形狀，但在這$L$秒中他的形狀會逐漸崩壞。因此對於某個接待行程，行程結束時間愈晚，TOI市形象所提升的外交形象就愈低。具體來說，接待一個$x_i$時刻出發並且需花$t_i$秒移動到巨無霸冰淇淋的人為TOI市外交形象帶來的增益是$C-(x_i+t_i)$，其中$C\geq L$。
請計算TOI市市長最多可以利用這支巨無霸冰淇淋提升多少的外交形象。
Input Format
第一行有一個正整數$T$，代表測資筆數。
接下來每一個測資中，第一行有三個正整數$N, L, C$，分別代表接待人數、冰淇淋可維持形狀的時間以及增益函數中的常數。之後的$N$行，每行會有兩個整數$x_i, t_i$，其中$0\leq x_i < L$，$1\leq t_i\leq L-x_i$，代表第$i$個人的出發時刻以及旅程所需時間。
Output Format
對於每筆測資，請輸出一行包含一個整數，代表TOI市市長可提升的外交形象最大值。
Sample Input 1
1 3 5
0 2
3 8 9
0 4
4 4
0 8
3 10 12
0 3
2 4
5 5
Sample Output 1
6
11
Hints
本題共有五組測試資料。每組可有多個輸入檔案，全部答對該組才得分。
第一組10分，$T\leq 10, N\leq 15, L\leq C\leq 10^ 9$
第二組10分，$T\leq 10, N\leq 10^ 5, L\leq 15, L\leq C\leq 10^ 9$
第三組20分，$T\leq 10, N\leq 10^ 3, L\leq C\leq 10^ 9$
第四組20分，$T\leq 10, N\leq 10^ 5, L\leq 10^ 3, L\leq C\leq 10^ 9$
第五組40分，$T\leq 10, N\leq 10^ 5, L\leq C\leq 10^ 9$
注意事項：
使用C++作答的同學，請在程式碼開頭加上#include<cstdio>，並利用scanf讀入資料、用printf輸出資料。使用cin / cout讀入/輸出資料可能會因為效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下：
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。
Problem Source
Problem Set / Description by Paupière
建國中學105學年度全國賽模擬賽pD
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 40 |