题目链接:http://codeforces.com/gym/102219/problem/C
Time limit per test 1.0 s Memory limit per test 256 MB

Description

Nina from the IT support needs your help with another daily puzzle she faces. She is able to take her lunch break anytime she wants. But because of limited capacity, she only can take S minutes based on the needs that day. Any extra minutes that she is late, she has to pay RM1 to the late jar.

She prepared a list of her favorite restaurants and how long it would take for her to lunch in each restaurant based on experience, (1 ≤ ti ≤ 109 ). She also assigned a value for each of the restaurants that shows how much extra she is willing to pay but still be happy, (1 ≤ fi ≤ 10^9 ).

For example, if she needs tx minutes to dine in restaurant x which she values RMfx . If tx≤S then she is fully happy and it is as if she saved RMfx.

But if tx>S she would save fx−(tx−S).

Please help her to find the restaurant that she would be happiest in and meanwhile save the most. Also, keep in mind she can choose exactly one restaurant to lunch each day.

Input

The first line contains an integer – D(1≤D≤10) – the number of days.

The second line contains two space-separated integers — N(1≤N≤104) and S(1≤S≤109) — the number of restaurants in Nina's list and her lunch break time for the day, correspondingly.

Each of the next N lines contains two space-separated integers — fi(1≤fi≤109) and ti (1≤ti≤109) — the characteristics of the ith restaurant.

Output

In a single line print a single integer — the maximum money she is saving/her happiness by day.

Example

input

2
2 5
3 3
4 5

1 5
1 7

output

Case #1: 4
Case #2: -1

Problem solving report:

Description: 给你一个总时间S和每个餐厅吃午餐的时间ti和愿意支付的额外费用fi，如果ti<=S，那么他会得到fi的幸福值，否则他会得到fi-(ti-S)的幸福值，求他在一个餐厅吃饭能得到的最大幸福值。
Problem solving: 直接判断求最大值就行了，注意有负数，初始值不能附为0。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int main() {
    int t, n, m, kase = 0;
    scanf("%d", &t);
    while (t--) {
        int max_ = -inf;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            if (v <= m)
                max_ = max(max_, u);
            else max_ = max(max_, u - (v - m));
        }
        printf("Case #%d: %d\n", ++kase, max_);
    }
    return 0;
}