Codeforces Round #169 (Div. 2) A水 B C区间更新 D 思路

Having written another programming contest, three Rabbits decided to grab some lunch. The coach gave the team exactly k time units for the lunch break.

The Rabbits have a list of n restaurants to lunch in: the i-th restaurant is characterized by two integers f_i and t_i. Value t_i shows the time the Rabbits need to lunch in the i-th restaurant. If time t_i exceeds the time k that the coach has given for the lunch break, then the Rabbits' joy from lunching in this restaurant will equal f_i - (t_i - k). Otherwise, the Rabbits get exactly f_i units of joy.

Your task is to find the value of the maximum joy the Rabbits can get from the lunch, depending on the restaurant. The Rabbits must choose exactly one restaurant to lunch in. Note that the joy value isn't necessarily a positive value.

Input

The first line contains two space-separated integers — n (1 ≤ n ≤ 10⁴) and k (1 ≤ k ≤ 10⁹) — the number of restaurants in the Rabbits' list and the time the coach has given them to lunch, correspondingly. Each of the next n lines contains two space-separated integers — f_i (1 ≤ f_i ≤ 10⁹) and t_i (1 ≤ t_i ≤ 10⁹) — the characteristics of the i-th restaurant.

Output

In a single line print a single integer — the maximum joy value that the Rabbits will get from the lunch.

Examples

Input

2 5
3 3
4 5

Output

Input

Output

Input

1 5
1 7

Output

-1
题意：水
题解：模拟

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <stack>
 7 #include <queue>
 8 #include <cmath>
 9 #include <map>
10 #define ll  __int64
11 #define mod 1000000007
12 #define dazhi 2147483647
13 using namespace  std;
14 ll n,k;
15 ll a,b;
16 ll ans=0;
17 int main()
18 {
19     ans=-1e10;
20     scanf("%I64d %I64d",&n,&k);
21     for(ll i=1;i<=n;i++)
22     {
23         scanf("%I64d %I64d",&a,&b);
24         if(b>k)
25             ans=max(ans,a-(b-k));
26         else
27             ans=max(ans,a);
28     }
29    printf("%I64d
",ans);
30     return 0;
31 }

The Little Girl loves problems on games very much. Here's one of them.

Two players have got a string s, consisting of lowercase English letters. They play a game that is described by the following rules:

The players move in turns; In one move the player can remove an arbitrary letter from string s.
If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins. A palindrome is a string that reads the same both ways (from left to right, and vice versa). For example, string "abba" is a palindrome and string "abc" isn't.

Determine which player will win, provided that both sides play optimally well — the one who moves first or the one who moves second.

Input

The input contains a single line, containing string s (1 ≤ |s| ≤ 10³). String s consists of lowercase English letters.

Output

In a single line print word "First" if the first player wins (provided that both players play optimally well). Otherwise, print word "Second". Print the words without the quotes.

Examples

Input

aba

Output

First

Input

abca

Output

Second
题意：给你一个字符串 两个人轮流删除一个字符 在删除之前 若重新组合字符的顺序  使得字符串为回文串 则当前选手获胜
题解：因为题目中说明字符串可以重新排列组合 所以只需要判断初始字符串中每个字符出现的次数 统计出现次数为奇数次的字母的个数 为0或为奇数则先手胜

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <stack>
 7 #include <queue>
 8 #include <cmath>
 9 #include <map>
10 #define ll  __int64
11 #define mod 1000000007
12 #define dazhi 2147483647
13 using namespace  std;
14 char a[1003];
15 map<char,int> mp;
16 int main()
17 {
18     scanf("%s",a);
19     int len=strlen(a);
20     for(int i=0;i<len;i++)
21     {
22         mp[a[i]]++;
23     }
24     int ans=0;
25     for(char i='a';i<='z';i++)
26     {
27         if(mp[i]%2)
28             ans++;
29     }
30     if(ans==0||ans%2)
31         printf("First
");
32     else
33         printf("Second
");
34     return 0;
35 }

The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of n elements (the elements of the array are indexed starting from 1); also, there are q queries, each one is defined by a pair of integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ n). You need to find for each query the sum of elements of the array with indexes from l_i to r_i, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

Input

The first line contains two space-separated integers n (1 ≤ n ≤ 2·10⁵) and q (1 ≤ q ≤ 2·10⁵) — the number of elements in the array and the number of queries, correspondingly.

The next line contains n space-separated integers a_i (1 ≤ a_i ≤ 2·10⁵) — the array elements.

Each of the following q lines contains two space-separated integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — the i-th query.

Output

In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

Output

Input

Output

33
题意：给你n个数 q个区间 问你如何排列这n个数 使得q个区间和的和最大 输出这个最大值
题解：统计每个位置在q个区间中出现的次数 升序排列 对于n个数升序排列 相乘求和
可以线段树区间更新单点查询 也可以利用区间更新的姿势。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <stack>
 7 #include <queue>
 8 #include <cmath>
 9 #include <map>
10 #define ll  __int64
11 #define mod 1000000007
12 #define dazhi 2147483647
13 using namespace  std;
14 ll n,q;
15 ll a[200005];
16 ll l,r;
17 ll s[200005];
18 ll ans=0;
19 struct node
20 {
21     ll w;
22 }N[200005];
23 bool cmp(struct node aa,struct node bb)
24 {
25     return aa.w<bb.w;
26 }
27 int main()
28 {
29     memset(s,0,sizeof(s));
30      scanf("%I64d %I64d",&n,&q);
31      for(ll i=1;i<=n;i++)
32         scanf("%I64d",&a[i]);
33      sort(a+1,a+1+n);
34      for(ll i=1;i<=q;i++)
35      {
36          scanf("%I64d %I64d",&l,&r);
37          s[l]++;
38          s[r+1]--;
39      }
40     ll exm=0;
41      for(ll i=1;i<=n;i++)
42      {
43          exm+=s[i];
44          N[i].w=exm;
45      }
46      sort(N+1,N+1+n,cmp);
47      for(ll i=1;i<=n;i++)
48         ans+=N[i].w*a[i];
49      printf("%I64d
",ans);
50     return 0;
51 }

A little girl loves problems on bitwise operations very much. Here's one of them.

You are given two integers l and r. Let's consider the values of $\text{[math]}$ for all pairs of integers a and b (l ≤ a ≤ b ≤ r). Your task is to find the maximum value among all considered ones.

Expression $\text{[math]}$ means applying bitwise excluding or operation to integers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is represented as "^", in Pascal — as «xor».

Input

The single line contains space-separated integers l and r (1 ≤ l ≤ r ≤ 10¹⁸).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

In a single line print a single integer — the maximum value of $\text{[math]}$ for all pairs of integers a, b (l ≤ a ≤ b ≤ r).

Examples

Input

1 2

Output

Input

8 16

Output

Input

1 1

Output

0
题意：给你一个区间 在区间任意选出两个数  输出最大的两数异或和
题解：数据范围最大为2^62  从高位到低位枚举 寻找上下界异或和为1的最高位

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <stack>
 7 #include <queue>
 8 #include <cmath>
 9 #include <map>
10 #define ll  __int64
11 #define mod 1000000007
12 #define dazhi 2147483647
13 using namespace  std;
14 ll l,r;
15 int main()
16 {
17     scanf("%I64d %I64d",&l,&r);
18     if(l==r)
19     {
20         printf("0
");
21         return 0;
22     }
23     ll ans=0;
24     ans=(ll)1<<62;
25     while(ans&&(ans&l)==(ans&r)) ans>>=1;
26     printf("%I64d
",ans*2-1);
27     return 0;
28 }