A. Contest for Robots

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp is preparing the first programming contest for robots. There are nn problems in it, and a lot of robots are going to participate in it. Each robot solving the problem ii gets pipi points, and the score of each robot in the competition is calculated as the sum of pipi over all problems ii solved by it. For each problem, pipi is an integer not less than 11.

Two corporations specializing in problem-solving robot manufacturing, "Robo-Coder Inc." and "BionicSolver Industries", are going to register two robots (one for each corporation) for participation as well. Polycarp knows the advantages and flaws of robots produced by these companies, so, for each problem, he knows precisely whether each robot will solve it during the competition. Knowing this, he can try predicting the results — or manipulating them.

For some reason (which absolutely cannot involve bribing), Polycarp wants the "Robo-Coder Inc." robot to outperform the "BionicSolver Industries" robot in the competition. Polycarp wants to set the values of pipi in such a way that the "Robo-Coder Inc." robot gets strictly more points than the "BionicSolver Industries" robot. However, if the values of pipi will be large, it may look very suspicious — so Polycarp wants to minimize the maximum value of pipi over all problems. Can you help Polycarp to determine the minimum possible upper bound on the number of points given for solving the problems?

Input

The first line contains one integer nn (1≤n≤1001≤n≤100) — the number of problems.

The second line contains nn integers r1r1, r2r2, ..., rnrn (0≤ri≤10≤ri≤1). ri=1ri=1 means that the "Robo-Coder Inc." robot will solve the ii-th problem, ri=0ri=0 means that it won't solve the ii-th problem.

The third line contains nn integers b1b1, b2b2, ..., bnbn (0≤bi≤10≤bi≤1). bi=1bi=1 means that the "BionicSolver Industries" robot will solve the ii-th problem, bi=0bi=0 means that it won't solve the ii-th problem.

Output

If "Robo-Coder Inc." robot cannot outperform the "BionicSolver Industries" robot by any means, print one integer −1−1.

Otherwise, print the minimum possible value of maxi=1npimaxi=1npi, if all values of pipi are set in such a way that the "Robo-Coder Inc." robot gets strictly more points than the "BionicSolver Industries" robot.

Examples

input

Copy

5
1 1 1 0 0
0 1 1 1 1

output

Copy

3

input

Copy

3
0 0 0
0 0 0

output

Copy

-1

input

Copy

4
1 1 1 1
1 1 1 1

output

Copy

-1

input

Copy

9
1 0 0 0 0 0 0 0 1
0 1 1 0 1 1 1 1 0

output

Copy

4

Note

In the first example, one of the valid score assignments is p=[3,1,3,1,1]p=[3,1,3,1,1]. Then the "Robo-Coder" gets 77 points, the "BionicSolver" — 66 points.

In the second example, both robots get 00 points, and the score distribution does not matter.

In the third example, both robots solve all problems, so their points are equal.

题目大意 ：

输入两组数，为1表示有该任务，0表示没有，现在由你定义每个任务的分数，使得最高分最小点情况下，第一个人的总分大于第二个人，如果无法满足，输出-1

思路 ：

先处理两个人的特有任务，如果第一个人特有的任务第二个人都有，那么一定无法满足，因为两个人任务的分数是相同的，第二个人特有的任务按照题目要求，应当为1分，第一个人的特有任务，按照第二个人特有任务的数量，平均分配就好，注意特判能够整除的情况

Accepted code

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

#define sc scanf
#define ls rt << 1
#define rs ls | 1
#define Min(x, y) x = min(x, y)
#define Max(x, y) x = max(x, y)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pir pair <int, int>
#define MK(x, y) make_pair(x, y)
#define MEM(x, b) memset(x, b, sizeof(x))
#define lowbit(x) ((x) & -(x))
#define P2(x) ((x) * (x))

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 100;
const int INF = 0x3f3f3f3f;
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }

int a[MAXN], b[MAXN], n;
int ans1, ans2; 

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	for (int i = 1; i <= n; i++) {
		if (a[i] && !b[i])
			ans1++;
		else if (!a[i] && b[i])
			ans2++;
	}
	if (ans1 == 0)
		cout << -1 << endl, exit(0);   // 第一个人特有任务
	if (ans1 > ans2)
		cout << 1 << endl, exit(0);   
	if (ans2 % ans1 == 0)
		cout << ans2 / ans1 + 1 << endl;
	else
		cout << (ans2 - 1) / ans1 + 1 << endl;
	return 0;  // 改数组大小!!!
}

                                                                              B. Journey Planning

 

Tanya wants to go on a journey across the cities of Berland. There are nn cities situated along the main railroad line of Berland, and these cities are numbered from 11 to nn.

Tanya plans her journey as follows. First of all, she will choose some city c1c1 to start her journey. She will visit it, and after that go to some other city c2>c1c2>c1, then to some other city c3>c2c3>c2, and so on, until she chooses to end her journey in some city ck>ck−1ck>ck−1. So, the sequence of visited cities [c1,c2,…,ck][c1,c2,…,ck] should be strictly increasing.

There are some additional constraints on the sequence of cities Tanya visits. Each city ii has a beauty value bibi associated with it. If there is only one city in Tanya's journey, these beauty values imply no additional constraints. But if there are multiple cities in the sequence, then for any pair of adjacent cities cici and ci+1ci+1, the condition ci+1−ci=bci+1−bcici+1−ci=bci+1−bci must hold.

For example, if n=8n=8 and b=[3,4,4,6,6,7,8,9]b=[3,4,4,6,6,7,8,9], there are several three possible ways to plan a journey:

• c=[1,2,4]c=[1,2,4];
• c=[3,5,6,8]c=[3,5,6,8];
• c=[7]c=[7] (a journey consisting of one city is also valid).

There are some additional ways to plan a journey that are not listed above.

Tanya wants her journey to be as beautiful as possible. The beauty value of the whole journey is the sum of beauty values over all visited cities. Can you help her to choose the optimal plan, that is, to maximize the beauty value of the journey?

Input

The first line contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of cities in Berland.

The second line contains nn integers b1b1, b2b2, ..., bnbn (1≤bi≤4⋅1051≤bi≤4⋅105), where bibi is the beauty value of the ii-th city.

Output

Print one integer — the maximum beauty of a journey Tanya can choose.

Examples

Input

6
10 7 1 9 10 15

Output

26

Input

1
400000

Output

400000

Input

7
8 9 26 11 12 29 14

Output

55

Note

The optimal journey plan in the first example is c=[2,4,5]c=[2,4,5].

The optimal journey plan in the second example is c=[1]c=[1].

The optimal journey plan in the third example is c=[3,6]c=[3,6].

题目大意 ：

有N个数，对于Ai和Aj这两个数，如果满足Ai - Aj = i - j，那么两个数就可以求和，输出整个数组能够求和的最大值

思路 ：

将题目给的式子移项变成，Ai - i = Aj - j，所以权值 - 下标相等的为一组，这样的话开一个map存一下就行了

Accepted code

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

#define sc scanf
#define ls rt << 1
#define rs ls | 1
#define Min(x, y) x = min(x, y)
#define Max(x, y) x = max(x, y)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pir pair <int, int>
#define MK(x, y) make_pair(x, y)
#define MEM(x, b) memset(x, b, sizeof(x))
#define lowbit(x) ((x) & -(x))
#define P2(x) ((x) * (x))

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 100;
const int INF = 0x3f3f3f3f;
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }

int n;
unordered_map <int, ll> mp;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		ll t;
		sc("%lld", &t);
		mp[t - i] += t;
	}
	ll max_ = -1;
	for (auto it : mp)
		Max(max_, it.second);
	cout << max_ << endl;
	return 0;  // 改数组大小!!!
}

                                                                                    C. Remove Adjacent

You are given a string ss consisting of lowercase Latin letters. Let the length of ss be |s||s|. You may perform several operations on this string.

In one operation, you can choose some index ii and remove the ii-th character of ss (sisi) if at least one of its adjacent characters is the previous letter in the Latin alphabet for sisi. For example, the previous letter for b is a, the previous letter for s is r, the letter a has no previous letters. Note that after each removal the length of the string decreases by one. So, the index ii should satisfy the condition 1≤i≤|s|1≤i≤|s| during each operation.

For the character sisi adjacent characters are si−1si−1 and si+1si+1. The first and the last characters of ss both have only one adjacent character (unless |s|=1|s|=1).

Consider the following example. Let s=s= bacabcab.

1. During the first move, you can remove the first character s1=s1= b because s2=s2= a. Then the string becomes s=s= acabcab.
2. During the second move, you can remove the fifth character s5=s5= c because s4=s4= b. Then the string becomes s=s= acabab.
3. During the third move, you can remove the sixth character s6=s6='b' because s5=s5= a. Then the string becomes s=s= acaba.
4. During the fourth move, the only character you can remove is s4=s4= b, because s3=s3= a (or s5=s5= a). The string becomes s=s= acaa and you cannot do anything with it.

Your task is to find the maximum possible number of characters you can remove if you choose the sequence of operations optimally.

Input

The first line of the input contains one integer |s||s| (1≤|s|≤1001≤|s|≤100) — the length of ss.

The second line of the input contains one string ss consisting of |s||s| lowercase Latin letters.

Output

Print one integer — the maximum possible number of characters you can remove if you choose the sequence of moves optimally.

Examples

Input

8
bacabcab

Output

4

Input

4
bcda

Output

3

Input

6
abbbbb

Output

5

Note

The first example is described in the problem statement. Note that the sequence of moves provided in the statement is not the only, but it can be shown that the maximum possible answer to this test is 44.

In the second example, you can remove all but one character of ss. The only possible answer follows.

1. During the first move, remove the third character s3=s3= d, ss becomes bca.
2. During the second move, remove the second character s2=s2= c, ss becomes ba.
3. And during the third move, remove the first character s1=s1= b, ss becomes a.

题目大意 ：

一个字符串，如果与某个位置相邻的字母，至少有一个比该位置的字母小1，那么该位置的字母就可以删掉，剩下的字母接上来，输出对于整个字符串，最多可以删多少个字母。

思路 ：

数据很小，可以直接暴力，不难想到先删字母大的，然后再删小的可以保证删的最多，所以就从 ‘z' 遍历到 ’a‘， 一个一个删，当前字母不能删就往前循环

Accepted code

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

#define sc scanf
#define ls rt << 1
#define rs ls | 1
#define Min(x, y) x = min(x, y)
#define Max(x, y) x = max(x, y)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pir pair <int, int>
#define MK(x, y) make_pair(x, y)
#define MEM(x, b) memset(x, b, sizeof(x))
#define lowbit(x) ((x) & -(x))
#define P2(x) ((x) * (x))

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 100;
const int INF = 0x3f3f3f3f;
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }

string str;
int n;

int main()
{
	cin >> n >> str;
	for (char i = 'z'; i >= 'b'; i--) {
		if (SZ(str) == 1)    // 无法删除
			break;
		while (true) {
			if (SZ(str) == 1)
				break;
			bool ok = false;
			for (int j = 0; j < SZ(str); j++) {
				if (str[j] != i)                  // 只删当前字母
					continue;
				if (j == 0) {                     // 开头字母相邻的要特判
					if (str[j + 1] == i - 1) {
						ok = true;
						str.erase(str.begin() + j, str.begin() + j + 1);
						break;
					}
				}
				else if (j == SZ(str) - 1) {      // 最后一个字母相邻的特判
					if (str[j - 1] == i - 1) {
						ok = true;
						str.erase(str.begin() + j, str.begin() + j + 1);
						break;
					}
				}
				else {
					if (str[j - 1] == i - 1 || str[j + 1] == i - 1) {
						ok = true;
						str.erase(str.begin() + j, str.begin() + j + 1);
						break;
					}
				}
			}
			if (!ok)
				break;
		}
	}
	cout << n - SZ(str) << endl;
	return 0;  // 改数组大小!!!
}

                                                                       D. Navigation System

The map of Bertown can be represented as a set of nn intersections, numbered from 11 to nn and connected by mm one-way roads. It is possible to move along the roads from any intersection to any other intersection. The length of some path from one intersection to another is the number of roads that one has to traverse along the path. The shortest path from one intersection vv to another intersection uu is the path that starts in vv, ends in uu and has the minimum length among all such paths.

Polycarp lives near the intersection ss and works in a building near the intersection tt. Every day he gets from ss to tt by car. Today he has chosen the following path to his workplace: p1p1, p2p2, ..., pkpk, where p1=sp1=s, pk=tpk=t, and all other elements of this sequence are the intermediate intersections, listed in the order Polycarp arrived at them. Polycarp never arrived at the same intersection twice, so all elements of this sequence are pairwise distinct. Note that you know Polycarp's path beforehand (it is fixed), and it is not necessarily one of the shortest paths from ss to tt.

Polycarp's car has a complex navigation system installed in it. Let's describe how it works. When Polycarp starts his journey at the intersection ss, the system chooses some shortest path from ss to tt and shows it to Polycarp. Let's denote the next intersection in the chosen path as vv. If Polycarp chooses to drive along the road from ss to vv, then the navigator shows him the same shortest path (obviously, starting from vv as soon as he arrives at this intersection). However, if Polycarp chooses to drive to another intersection ww instead, the navigator rebuilds the path: as soon as Polycarp arrives at ww, the navigation system chooses some shortest path from ww to tt and shows it to Polycarp. The same process continues until Polycarp arrives at tt: if Polycarp moves along the road recommended by the system, it maintains the shortest path it has already built; but if Polycarp chooses some other path, the system rebuilds the path by the same rules.

Here is an example. Suppose the map of Bertown looks as follows, and Polycarp drives along the path [1,2,3,4][1,2,3,4] (s=1s=1, t=4t=4):

Check the picture by the link http://tk.codeforces.com/a.png

1. When Polycarp starts at 11, the system chooses some shortest path from 11 to 44. There is only one such path, it is [1,5,4][1,5,4];
2. Polycarp chooses to drive to 22, which is not along the path chosen by the system. When Polycarp arrives at 22, the navigator rebuilds the path by choosing some shortest path from 22 to 44, for example, [2,6,4][2,6,4] (note that it could choose [2,3,4][2,3,4]);
3. Polycarp chooses to drive to 33, which is not along the path chosen by the system. When Polycarp arrives at 33, the navigator rebuilds the path by choosing the only shortest path from 33 to 44, which is [3,4][3,4];
4. Polycarp arrives at 44 along the road chosen by the navigator, so the system does not have to rebuild anything.

Overall, we get 22 rebuilds in this scenario. Note that if the system chose [2,3,4][2,3,4] instead of [2,6,4][2,6,4] during the second step, there would be only 11 rebuild (since Polycarp goes along the path, so the system maintains the path [3,4][3,4] during the third step).

The example shows us that the number of rebuilds can differ even if the map of Bertown and the path chosen by Polycarp stays the same. Given this information (the map and Polycarp's path), can you determine the minimum and the maximum number of rebuilds that could have happened during the journey?

Input

The first line contains two integers nn and mm (2≤n≤m≤2⋅1052≤n≤m≤2⋅105) — the number of intersections and one-way roads in Bertown, respectively.

Then mm lines follow, each describing a road. Each line contains two integers uu and vv (1≤u,v≤n1≤u,v≤n, u≠vu≠v) denoting a road from intersection uu to intersection vv. All roads in Bertown are pairwise distinct, which means that each ordered pair (u,v)(u,v) appears at most once in these mm lines (but if there is a road (u,v)(u,v), the road (v,u)(v,u) can also appear).

The following line contains one integer kk (2≤k≤n2≤k≤n) — the number of intersections in Polycarp's path from home to his workplace.

The last line contains kk integers p1p1, p2p2, ..., pkpk (1≤pi≤n1≤pi≤n, all these integers are pairwise distinct) — the intersections along Polycarp's path in the order he arrived at them. p1p1 is the intersection where Polycarp lives (s=p1s=p1), and pkpk is the intersection where Polycarp's workplace is situated (t=pkt=pk). It is guaranteed that for every i∈[1,k−1]i∈[1,k−1] the road from pipi to pi+1pi+1 exists, so the path goes along the roads of Bertown.

Output

Print two integers: the minimum and the maximum number of rebuilds that could have happened during the journey.

Examples

Input

6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4

Output

1 2

Input

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

Output

0 0

Input

8 13
8 7
8 6
7 5
7 4
6 5
6 4
5 3
5 2
4 3
4 2
3 1
2 1
1 8
5
8 7 5 2 1

Output

0 3

这道题比赛的时候读错了题T_T，补题的时候也想了很久没做出来（题都错了咋可能做对），后来理解了正确的题意就马上给秒了

题目大意 ：

给你一个有向图和一条路径，你可以脑补出一个导航系统，每到一个点，就能显示出从该点到终点的最短路，最短路不一定唯一，所以导航的路线也可能不唯一，如果你下一个点走的仍然是你当前显示的最短路上的点，那么导航到下一个点就没有改变，最后输出导航显示最短路最少和最多的可能变化次数。

思路 ：

导航改变的原因，就是因为最短路不唯一，考虑下最少改变次数，一定是你没有按照上一次的最短路走，也就是说，你这次所在的点，到终点的最短路 ≥ 上一个点到终点的最短路，最多改变次数，多出来的就是当前是最短路，但是不唯一，这样的话，很容易想到反向建图，求出终点到每个点的最短路实际上就是每个点到终点的最短路，过程中dp一下，将不唯一的标记出来，因为边权都是1，所以先到的一定先标记，不用考虑从其他地方到该点更短了。

Accepted code

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

#define sc scanf
#define ls rt << 1
#define rs ls | 1
#define Min(x, y) x = min(x, y)
#define Max(x, y) x = max(x, y)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pir pair <int, int>
#define MK(x, y) make_pair(x, y)
#define MEM(x, b) memset(x, b, sizeof(x))
#define lowbit(x) ((x) & -(x))
#define P2(x) ((x) * (x))

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 100;
const int INF = 0x3f3f3f3f;
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }

vector <int> G[MAXN];
int dis[MAXN], dp[MAXN], n, m;
int pre[MAXN], k;
bool vis[MAXN];

void bfs(int x) {
	queue <int> q;
	MEM(dis, INF); dis[x] = 0;
	q.push(x);
	while (!q.empty()) {
		int ui = q.front();
		q.pop();
		if (vis[ui])
			continue;
		vis[ui] = true;
		for (auto it : G[ui]) {
			int vi = it;
			if (dis[vi] == dis[ui] + 1)
				dp[vi]++;
			Min(dis[vi], dis[ui] + 1);
			if (!vis[vi])
				q.push(vi);
		}
	}
}

int main()
{
	//freopen("D:/input.txt", "r", stdin);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int ui, vi;
		sc("%d %d", &ui, &vi);    // 多到一，反向建边即可
		G[vi].push_back(ui);
	}
	cin >> k;
	for (int i = 1; i <= k; i++)
		sc("%d", &pre[i]);
	bfs(pre[k]);
	int ans1 = 0, ans2 = 0;
	for (int i = 1; i < k; i++) {
		if (dis[pre[i + 1]] >= dis[pre[i]])  // 没走最短路，必须改变
			ans1++, ans2++;
		else if (dp[pre[i]])               // 最短路不唯一，可能改变
			ans2++;
	}
	cout << ans1 << " " << ans2 << endl;
	return 0;  // 改数组大小!!!
}