---

A.Regular bracket sequence

A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular if it it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are regular bracket sequences; "))" and ")((" are bracket sequences (but not regular ones), and "(a)" and "(1)+(1)" are not bracket sequences at all.

You have a number of strings; each string is a bracket sequence of length 22. So, overall you have cnt1cnt1 strings "((", cnt2cnt2 strings "()", cnt3cnt3 strings ")(" and cnt4cnt4strings "))". You want to write all these strings in some order, one after another; after that, you will get a long bracket sequence of length 2(cnt1+cnt2+cnt3+cnt4)2(cnt1+cnt2+cnt3+cnt4). You wonder: is it possible to choose some order of the strings you have such that you will get a regular bracket sequence? Note that you may not remove any characters or strings, and you may not add anything either.

Input

The input consists of four lines, ii-th of them contains one integer cnticnti (0≤cnti≤1090≤cnti≤109).

Output

Print one integer: 11 if it is possible to form a regular bracket sequence by choosing the correct order of the given strings, 00 otherwise.

Examples

Input

3
1
4
3

Output

1

Input

0
0
0
0

Output

1

Input

1
2
3
4

Output

0

In the first example it is possible to construct a string "(())()(()((()()()())))", which is a regular bracket sequence.

In the second example it is possible to construct a string "", which is a regular bracket sequence.

---

题解：水题。。。

参考代码： 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define clr(a,v) memset(a,v,sizeof(a))
 4 #define PI acos(-1.0)
 5 #define PII pair<int,int>
 6 #define pb push_back
 7 #define fi first
 8 #define se second
 9 typedef long long ll;
10 const int INF=0x3f3f3f3f;
11 int n1,n2,n3,n4;
12 int main()
13 {
14     cin>>n1>>n2>>n3>>n4;
15     if(n1!=n4) puts("0");
16     else
17     {
18         if(n1==0)
19         {
20             if(n3!=0) puts("0");
21             else puts("1");
22         }
23         else puts("1");
24     }
25     
26     return 0;
27 }

View Code

B.Discount

You came to a local shop and want to buy some chocolate bars. There are nn bars in the shop, ii-th of them costs aiai coins (and you want to buy all of them).

You have mm different coupons that allow you to buy chocolate bars. ii-th coupon allows you to buy qiqi chocolate bars while you have to pay only for the qi−1qi−1 most expensive ones (so, the cheapest bar of those qiqi bars is for free).

You can use only one coupon; if you use coupon ii, you have to choose qiqi bars and buy them using the coupon, and buy all the remaining n−qin−qi bars without any discounts.

To decide which coupon to choose, you want to know what will be the minimum total amount of money you have to pay if you use one of the coupons optimally.

Input

The first line contains one integer nn (2≤n≤3⋅1052≤n≤3⋅105) — the number of chocolate bars in the shop.

The second line contains nn integers a1a1, a2a2, ..., anan (1≤ai≤1091≤ai≤109), where aiai is the cost of ii-th chocolate bar.

The third line contains one integer mm (1≤m≤n−11≤m≤n−1) — the number of coupons you have.

The fourth line contains mm integers q1q1, q2q2, ..., qmqm (2≤qi≤n2≤qi≤n), where qiqi is the number of chocolate bars you have to buy using ii-th coupon so that the least expensive of them will be for free. All values of qiqi are pairwise distinct.

Output

Print mm integers, ii-th of them should be the minimum amount of money you have to pay if you buy qiqi bars with ii-th coupon, and all the remaining bars one by one for their full price.

Example

Input

7
7 1 3 1 4 10 8
2
3 4

Output

27
30

Consider the first example.

If we use the first coupon, we may choose chocolate bars having indices 11, 66 and 77, and we pay 1818 coins for them and 99 coins for all other bars.

If we use the second coupon, we may choose chocolate bars having indices 11, 55, 66 and 77, and we pay 2525 coins for them and 55 coins for all other bars.

 

 

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define clr(a,v) memset(a,v,sizeof(a))
 4 #define PI acos(-1.0)
 5 #define PII pair<int,int>
 6 #define pb push_back
 7 #define fi first
 8 #define se second
 9 typedef long long ll;
10 const int INF=0x3f3f3f3f;
11 const int maxn=3e5+10;
12 int n,m,a[maxn],q;
13 ll sum;
14 
15 int main()
16 {
17     scanf("%d",&n);
18     for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
19     scanf("%d",&m);
20     sort(a+1,a+1+n);
21     for(int i=1;i<=m;++i)
22     {
23         scanf("%d",&q);
24         ll ans=sum-a[n-q+1];
25         printf("%lld\n",ans);
26     }
27     
28     
29     return 0;
30 }

View Code

C.Painting the fence

You have a long fence which consists of nn sections. Unfortunately, it is not painted, so you decided to hire qq painters to paint it. ii-th painter will paint all sections xx such that li≤x≤rili≤x≤ri.

Unfortunately, you are on a tight budget, so you may hire only q−2q−2 painters. Obviously, only painters you hire will do their work.

You want to maximize the number of painted sections if you choose q−2q−2 painters optimally. A section is considered painted if at least one painter paints it.

Input

The first line contains two integers nn and qq (3≤n,q≤50003≤n,q≤5000) — the number of sections and the number of painters availible for hire, respectively.

Then qq lines follow, each describing one of the painters: ii-th line contains two integers lili and riri (1≤li≤ri≤n1≤li≤ri≤n).

Output

Print one integer — maximum number of painted sections if you hire q−2q−2 painters.

Examples

Input

7 5
1 4
4 5
5 6
6 7
3 5

Output

7

Input

4 3
1 1
2 2
3 4

Output

2

Input

4 4
1 1
2 2
2 3
3 4

Output

3

---

题解：题意就是给你n段区间，然后给你一个大区间，让你用最多n-2段小区间去覆盖大区间，问你：最多可以覆盖大区间多少个点；
我们先按区间右侧从小到大排序；记录每一个点覆盖的次数为1和2的点；
然后暴力O（n^2）枚举2个小区间，分别处理呗覆盖1和2的点即可；

参考代码：

 1 #include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<algorithm>
 8 using namespace std;
 9 #define clr(a,v) memset(a,v,sizeof(a))
10 #define PI acos(-1.0)
11 #define PII pair<int,int>
12 #define pb push_back
13 #define fi first
14 #define se second
15 typedef pair<int,int> pii;
16 typedef long long ll;
17 const int maxn=5010;
18 int l[maxn],r[maxn],cnt[maxn],sum[2][maxn];
19 pii sa[maxn];
20 int main()
21 {
22     int n,q;
23     scanf("%d%d",&n,&q);
24     clr(cnt,0);clr(sum,0);
25     for(int i=1;i<=q;++i)
26     {
27         scanf("%d%d",&l[i],&r[i]);
28         sa[i].fi=r[i];sa[i].se=l[i];
29         for(int j=l[i];j<=r[i];++j) cnt[j]++;
30     }
31     sort(sa+1,sa+1+q);
32     for(int i=1;i<=n;++i)
33     {
34         sum[0][i]=sum[0][i-1];
35         sum[1][i]=sum[1][i-1];
36         if(cnt[i]==1) sum[0][i]++;
37         if(cnt[i]==2) sum[1][i]++;
38     }
39     for(int i=1;i<=q;++i) r[i]=sa[i].fi,l[i]=sa[i].se;
40     int ans=0;
41     for(int i=1;i<=n;++i) {if(cnt[i]) ans++;}
42     int cans=ans;
43     for(int i=1;i<=q;++i)
44     {
45         for(int j=i+1;j<=q;++j)
46         {
47             if(l[j]>r[i]) cans=min(cans,(sum[0][r[i]]-sum[0][l[i]-1])+(sum[0][r[j]]-sum[0][l[j]-1]));
48             else if(l[j]<=r[i]&&l[j]>=l[i]) cans=min(cans,(sum[0][r[j]]-sum[0][l[i]-1])+(sum[1][r[i]]-sum[1][l[j]-1]));
49             else cans=min(cans,(sum[0][r[j]]-sum[0][l[j]-1])+(sum[1][r[i]]-sum[1][l[i]-1]));
50         }
51     }
52     printf("%d\n",ans-cans);
53     return 0;
54 }
55     
56     
57         

View Code

D.Stressful Training

Berland SU holds yet another training contest for its students today. nn students came, each of them brought his laptop. However, it turned out that everyone has forgot their chargers!

Let students be numbered from 11 to nn. Laptop of the ii-th student has charge aiai at the beginning of the contest and it uses bibi of charge per minute (i.e. if the laptop has cc charge at the beginning of some minute, it becomes c−bic−bi charge at the beginning of the next minute). The whole contest lasts for kk minutes.

Polycarp (the coach of Berland SU) decided to buy a single charger so that all the students would be able to successfully finish the contest. He buys the charger at the same moment the contest starts.

Polycarp can choose to buy the charger with any non-negative (zero or positive) integer power output. The power output is chosen before the purchase, it can't be changed afterwards. Let the chosen power output be xx. At the beginning of each minute (from the minute contest starts to the last minute of the contest) he can plug the charger into any of the student's laptops and use it for some integernumber of minutes. If the laptop is using bibi charge per minute then it will become bi−xbi−x per minute while the charger is plugged in. Negative power usage rate means that the laptop's charge is increasing. The charge of any laptop isn't limited, it can become infinitely large. The charger can be plugged in no more than one laptop at the same time.

The student successfully finishes the contest if the charge of his laptop never is below zero at the beginning of some minute (from the minute contest starts to the last minute of the contest, zero charge is allowed). The charge of the laptop of the minute the contest ends doesn't matter.

Help Polycarp to determine the minimal possible power output the charger should have so that all the students are able to successfully finish the contest. Also report if no such charger exists.

Input

The first line contains two integers nn and kk (1≤n≤2⋅1051≤n≤2⋅105, 1≤k≤2⋅1051≤k≤2⋅105) — the number of students (and laptops, correspondigly) and the duration of the contest in minutes.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤10121≤ai≤1012) — the initial charge of each student's laptop.

The third line contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤1071≤bi≤107) — the power usage of each student's laptop.

Output

Print a single non-negative integer — the minimal possible power output the charger should have so that all the students are able to successfully finish the contest.

If no such charger exists, print -1.

Examples

Input

2 4
3 2
4 2

Output

5

Input

1 5
4
2

Output

1

Input

1 6
4
2

Output

2

Input

2 2
2 10
3 15

Output

-1

Let's take a look at the state of laptops in the beginning of each minute on the first example with the charger of power 55:

1. charge: [3,2][3,2], plug the charger into laptop 1;
2. charge: [3−4+5,2−2]=[4,0][3−4+5,2−2]=[4,0], plug the charger into laptop 2;
3. charge: [4−4,0−2+5]=[0,3][4−4,0−2+5]=[0,3], plug the charger into laptop 1;
4. charge: [0−4+5,3−2]=[1,1][0−4+5,3−2]=[1,1].

The contest ends after the fourth minute.

However, let's consider the charger of power 44:

1. charge: [3,2][3,2], plug the charger into laptop 1;
2. charge: [3−4+4,2−2]=[3,0][3−4+4,2−2]=[3,0], plug the charger into laptop 2;
3. charge: [3−4,0−2+4]=[−1,2][3−4,0−2+4]=[−1,2], the first laptop has negative charge, thus, the first student doesn't finish the contest.

In the fourth example no matter how powerful the charger is, one of the students won't finish the contest.

---

题解：二分答案；
参考代码：

 1 #include <bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 
 5 const int maxN = 200010;
 6 int a[maxN], b[maxN];
 7 int n, k;
 8 
 9 bool ok(int m) {
10     set<int> rest;
11     for (int i = 0; i < k; i++)
12         rest.insert(i);
13     for (int i = 0; i < n; i++) {
14         for (int t = a[i]; t / b[i] < k; t += m) {
15             auto it = rest.upper_bound(t / b[i]);
16             if (it == rest.begin())
17                 return false;
18             rest.erase(--it);
19         }
20     }
21     return true;
22 }
23 
24 signed main() {
25     ios::sync_with_stdio(false);
26     cin >> n >> k; --k;
27     for (int i = 0; i < n; i++)
28         cin >> a[i];
29     for (int i = 0; i < n; i++)
30         cin >> b[i];
31     int l = -1, r = 2e12;
32     while (l + 1 != r) {
33         int m = (l + r) / 2;
34         ok(m) ? r = m : l = m;
35     }
36     cout << (ok(r) ? r : -1) << endl;
37     return 0;
38 }

View Code

E.Knapsack

You have a set of items, each having some integer weight not greater than 88. You denote that a subset of items is good if total weight of items in the subset does not exceed WW.

You want to calculate the maximum possible weight of a good subset of items. Note that you have to consider the empty set and the original set when calculating the answer.

Input

The first line contains one integer WW (0≤W≤10180≤W≤1018) — the maximum total weight of a good subset.

The second line denotes the set of items you have. It contains 88 integers cnt1cnt1, cnt2cnt2, ..., cnt8cnt8 (0≤cnti≤10160≤cnti≤1016), where cnticnti is the number of items having weight iiin the set.

Output

Print one integer — the maximum possible weight of a good subset of items.

Examples

Input

10
1 2 3 4 5 6 7 8

Output

10

Input

0
0 0 0 0 0 0 0 0

Output

0

Input

3
0 4 1 0 0 9 8 3

Output

3

---

题解：题意就是给你8个数，第i个数代表i有多少个；给你你个数n;
然后让你求：由这些数组成小与等于n的最大值是多少；
dfs搜索，从大到小搜；
参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const double PI = acos(-1.0);
 5 const double eps = 1e-6;
 6 const int INF = 0x3f3f3f3f;
 7 ll W,ans,cnt[9];
 8 void work(ll &a,ll b){if(a<b) a=b;}
 9 void dfs(ll x,ll now)
10 {
11     if(x==9){work(ans,now);return ;}
12     for(ll i=9,v=min((W-now)/x,1ll*cnt[x]);i;--i,--v) dfs(x+1,now+max(0*1ll,v*x));
13 }
14 int main() 
15 {
16     scanf("%lld",&W); ans=0;
17     for(int i=1;i<=8;++i) scanf("%lld",&cnt[i]);
18     dfs(1,0);
19     printf("%lld\n",ans);
20     return 0;
21 }

View Code

F.Clear String

You are given a string ss of length nn consisting of lowercase Latin letters. You may apply some operations to this string: in one operation you can delete some contiguous substring of this string, if all letters in the substring you delete are equal. For example, after deleting substring bbbb from string abbbbaccdd we get the string aaccdd.

Calculate the minimum number of operations to delete the whole string ss.

Input

The first line contains one integer nn (1≤n≤5001≤n≤500) — the length of string ss.

The second line contains the string ss (|s|=n|s|=n) consisting of lowercase Latin letters.

Output

Output a single integer — the minimal number of operation to delete string ss.

Examples

Input

5
abaca

Output

3

Input

8
abcddcba

Output

4

---

题解：题意就是你每次可以将一段区间的颜色变为一种颜色；
问你：变成给定样子最少需要多少步；
数位DP；
dp[i][j]:表示把i~j处理好至少需要多少次；
转移方程：
dp[l][r]=min(dp[l][r],dp[l+1][r]+(s[l]!=s[l+1])); 
dp[l][r]=min(dp[l][r],dp[l+1][r]+(s[l]!=s[r]));
dp[l][r]=min(dp[l][r],dp[l][r-1]+(s[r]!=s[r-1])); 
dp[l][r]=min(dp[l][r],dp[l][r-1]+(s[l]!=s[r]));

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int INF=0x3f3f3f3f;
 4 int dp[510][510],n;
 5 char s[510];
 6 
 7 int main()
 8 {
 9     scanf("%d",&n); scanf("%s",s+1);
10     for(int i=1;i<=n;++i) dp[i][i]=1;
11     for(int i=2;i<=n;++i)
12     {
13         for(int l=1;l<=n-i+1;++l)
14         {
15             int r=l+i-1;
16             dp[l][r]=INF;
17             dp[l][r]=min(dp[l][r],dp[l+1][r]+(s[l]!=s[l+1]));
18             dp[l][r]=min(dp[l][r],dp[l+1][r]+(s[l]!=s[r]));
19             
20             dp[l][r]=min(dp[l][r],dp[l][r-1]+(s[r]!=s[r-1]));
21             dp[l][r]=min(dp[l][r],dp[l][r-1]+(s[l]!=s[r]));
22             for(int j=l;j<=r-1;++j) dp[l][r]=min(dp[l][r],dp[l][j]+dp[j+1][r]);
23         }    
24     }
25     printf("%d\n",dp[1][n]);
26     return 0;
27 }

View Code