A. Contest for Robots

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$ i$ gets$ p_i$ points, and the score of each robot in the competition is calculated as the sum of pip_i over all problems$ i$ solved by it. For each problem, pip_i is an integer not less than$ 1$.
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 pip_i in such a way that the “Robo-Coder Inc.” robot gets strictly more points than the “BionicSolver Industries” robot. However, if the values of pip_i will be large, it may look very suspicious — so Polycarp wants to minimize the maximum value of pip_i 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 n(1≤n≤100)n (1≤n≤100) — the number of problems.
The second line contains$ n$ integers$ r_1, r_2, …, r_n (0≤r_i≤1)$. ri=1r_i=1 means that the “Robo-Coder Inc.” robot will solve the ii-th problem,$ r_i=0$ means that it won’t solve the $ i$-th problem.
The third line contains nn integers b1,b2,...,bn(0≤bi≤1)b_1, b_2, ..., b_n (0≤b_i≤1). bi=1b_i=1 means that the “BionicSolver Industries” robot will solve the ii-th problem, $b_i=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 max⁡i=1npi\max \limits_{i = 1}^{n} p_i, if all values of$ p_i$ are set in such a way that the “Robo-Coder Inc.” robot gets strictly more points than the “BionicSolver Industries” robot.

Examples

input

5
1 1 1 0 0
0 1 1 1 1

output

3

input

3
0 0 0
0 0 0

output

-1

input

4
1 1 1 1
1 1 1 1

output

-1

input

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

output

4

Note

In the first example, one of the valid score assignments is$ p=[3,1,3,1,1]$. Then the “Robo-Coder” gets 77 points, the “BionicSolver” — 66 points.
In the second example, both robots get$ 0$ points, and the score distribution does not matter.
In the third example, both robots solve all problems, so their points are equal.

Translation

两个机器人比赛，已知两个机器人分别会做出哪几道题，设计每一题的分数，使得第一个机器人赢，要求所有题目分数最大值最小化。

Idea

我们不会关心平局，只会关心能分出胜负的题目。假设第一个机器人能答出而第二个机器人不能答出的题目有c1c_1，而第二个机器人能答出而第一个机器人不能答出的题目有c2c_2，两者平局的题有c3c_3显然，当c3=nc_3=n，那么无论怎么改变两者最后都是平局；当c3<nc_3<n如果c1>c2c_1>c_2，那么只需要将每道题设置为1；如果c1=c2c_1=c_2，那么将其中某一道题设置为2就能使第一个机器人胜出；如果c1<c2c_1<c_2，假如c1=0c_1=0的话，那么第一个机器人必输，假如c1>0c_1>0，那么我们将所有c2c_2设置为1分，将c2c_2分平均分配到c1c_1个题中即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
void solve()
{
	int a[110];
	int b[110];
	int i;
	int n;
	cin>>n;
	int c1=0,c2=0,c3=0;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=n;i++) cin>>b[i];
	for(i=1;i<=n;i++)
	{
		if(a[i]&&!b[i]) c1++;
		if(!a[i]&&b[i]) c2++;
		if(a[i]==b[i]) c3++;
	}
	int ans;
	if(c3==n) ans=-1;
	else
	{
		if(c1>c2) ans=1;
		else if(c1<c2)
		{
			if(!c1) ans=-1;
			else ans=c2/c1+1;
		}
		else ans=2;
	} 
	cout<<ans;
}
int main()
{
	solve();
	return 0;
}

B. Journey Planning

Tanya wants to go on a journey across the cities of Berland. There are n cities situated along the main railroad line of Berland, and these cities are numbered from 11 to $ n$.
Tanya plans her journey as follows. First of all, she will choose some city c1 to start her journey. She will visit it, and after that go to some other city c2>c1c_2>c_1, then to some other city c3>c2c_3>c_2, and so on, until she chooses to end her journey in some city ck>ck−1c_k>c_{k−1}. So, the sequence of visited cities$ [c_1,c_2,…,c_k]$ should be strictly increasing.
There are some additional constraints on the sequence of cities Tanya visits. Each city i has a beauty value bi 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 cic_i and ci+1c_{i+1}, the condition $c_{i+1}−c_i=b_{c_{i+1}}−b_{c_i}$ 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 n(1≤n≤2⋅105)n (1≤n≤2⋅10^5) — the number of cities in Berland.
The second line contains nn integers $ b_1, b_2, …, b_n (1≤b_i≤4⋅10^5)$, where bib_i 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]$.
The optimal journey plan in the second example is $ c=[1]$.
The optimal journey plan in the third example is c=[3,6]c=[3,6].

Translation

给一个有nn个元素的数组bb，请设计一个含mm个元素的数组cc，要求满足$c_{i+1}−c_i=b_{c_{i+1}}−b_{c_i}$，输出满足条件的$\sum\limits_{i = 1}^m {{b_{{c_i}}}} $的最大值。

Idea

$c_{i+1}−c_i=b_{c_{i+1}}−b_{c_i} \Leftrightarrow b_{c_{i+1}}-c_{i+1}=b_{c_i}-c_i$

翻译成人话，cc中的所有元素cic_i使得bci−ci=constb_{c_i}-c_i=const，也就是说要选取的是bb中bi−ib_i-i相同的ii分成一组，每一组分别组成一个数列cc，我们只要找到其中最大的$\sum\limits_{i = 1}^m {{b_{{c_i}}}} $即可，由于可能性较多，可以用map作离散化处理，也可实现去重。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<map>
using namespace std;
const int N=200006;
long long b[N],opt[N];
map<long long,long long>cnt;
long long solve()
{
	int n;
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>b[i];
	for(i=1;i<=n;i++) 
	{
		opt[i]=b[i]-i;
		cnt[opt[i]]+=b[i];//选取相同的b[i]-i
	}
	map<long long,long long>::iterator it;
	long long ans=0;
	//迭代器访问
	for(it=cnt.begin();it!=cnt.end();it++) ans=max(ans,it->second);
	return ans;
}
int main()
{
	cout<<solve();
	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 s(si)s (s_i) if at least one of its adjacent characters is the previous letter in the Latin alphabet for sis_i. 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 iishould satisfy the condition 1≤i≤∣s∣1≤i≤|s| during each operation.
For the character sis_i adjacent characters are si−1s_i−1 and si+1s_i+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 ss= “bacabcab”.

  1. During the first move, you can remove the first character s1s_1=‘b’ because s2s_2= ‘a’. Then the string becomes ss= “acabcab”.
  2. During the second move, you can remove the fifth character s5s_5= ‘c’ because s4s_4= ‘b’. Then the string becomes ss=“acabab”.
  3. During the third move, you can remove the sixth character s6s_6=‘b’ because s5s_5= ‘a’. Then the string becomes ss= “acaba”.
  4. During the fourth move, the only character you can remove is s4s_4= ‘b’, because s3s_3= ‘a’ (or s5s_5= ‘a’). The string becomes ss= “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∣(1≤∣s∣≤100)|s| (1≤|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.

  • During the first move, remove the third character s3s_3= d,ss becomes bca.
  • During the second move, remove the second character s2s_2= c, ss becomes ba.
  • And during the third move, remove the first character s1s_1= b, ss becomes a.

Translation

给一个长度为∣s∣|s|的字符串ss，对于其中的每一个字符sis_i若相邻的字符只要其中一个是si−1s_i-1，那么就可以将sis_i从其中去掉，问最多可以去掉几个字符。

Idea

每次去除的sis_i必须是所有满足条件(存在si−1=si−1s_{i-1}=s_i-1或si+1=si−1s_{i+1}=s_i-1)的字符中最大的那个个，只需要每次进行一步这的贪心计算，直到不能改动为止。
因为字符串较短，允许每一次去除操作后扫描一遍剩余字符串，寻找到满足条件的最大sis_i。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<string>
using namespace std;
int solve()
{
	int n;
	string s;
	char maxx;
	cin>>n>>s;
	int i;
	int pos;
	while(true)
	{
		pos=-1;
		maxx=NULL;
		for(i=0;i<s.size();i++)
		{
			if(i-1>=0&&s[i]-s[i-1]==1)
			{
				if(s[i]>maxx)//更新最大的s[i]
				{
					pos=i;
					maxx=s[i];
				}
			}
			if(i+1<s.size()&&s[i]-s[i+1]==1)
			{
				if(s[i]>maxx)
				{
					pos=i;
					maxx=s[i];
				}
			}
		}
		if(pos==-1) break;//没有找到满足条件的s[i]
		else s.erase(pos,1);
	}
	return n-s.size();
}
int main()
{
	cout<<solve();
	return 0;
}

D. Navigation System

The map of Bertown can be represented as a set of n 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 vvto 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: p1,p2,...,pkp_1, p_2, ..., p_k, where p1=s,pk=tp_1=s, p_k=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=1,t=4s=1, t=4):

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];
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]);
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];
Polycarp arrives at 4 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⋅105)(2≤n≤m≤2⋅10^5) — 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≤n,u≠v)(1≤u,v≤n, u≠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 k(2≤k≤n)k (2≤k≤n) — the number of intersections in Polycarp’s path from home to his workplace.
The last line contains kk integers $p_1, p_2, …, p_k $(1≤pi≤n1≤p_i≤n, all these integers are pairwise distinct) — the intersections along Polycarp’s path in the order he arrived at them. p1p_1 is the intersection where Polycarp lives (s=p1s=p_1), and pkp_k is the intersection where Polycarp’s workplace is situated (t=pkt=p_k). It is guaranteed that for every i∈[1,k−1]i\in [1,k−1] the road from pip_i to pi+1p_{i+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

Translation

给一个nn个节点，mm条边的有向图，Polycarp想从p1p_1走到pkp_k，中间经过p2,p3,...,pk−1p_2,p_3,...,p_{k-1}。Polycarp有一个导航，他从p1p_1出发，导航已经规划了从p1p_1到pkp_k的最短路径，但是Polycarp会按照自己想好的路线走，他想的路线和导航想的路线可能不一样，这时导航就会重新规划(rebuild)最短路线。求重新规划路线的最小值和最大值。

Idea

首先解答一个问题，重新规划路线的次数为什么会有最大值和最小值。我们不妨来看看题中所给的例子。

最短路是[1,5,4][1,5,4]，但是Polycarp走到了22去，于是就重新规划了路线，这时的最短路有两条，即[2,6,4][2,6,4] 和 [2,3,4][2,3,4];如果选择[2,6,4][2,6,4]，Polycarp会再次偏离路线，然后导航又会重新规划路线；如果选[2,3,4][2,3,4]，这和Polycarp想的一样，这样导航就不会重新规划路线了。
通过上面的例子可以看到，当在pip_i需要重新规划路线时,minmin和maxmax都会增加11；若不需要规划路线但是最短路不止一条，minmin选择的是最接近Polycarp的路线的最短路，maxmax选择的是偏离Polycarp的路线的最短路，因此maxmax还会再加11。
我们可以建一个反图，通过一次BFSBFS得到所有点到pkp_k的最短路径长度dis[i]dis[i]，当pip_i不是pi+1p_{i+1}的父亲节点，说明走的就不是最短路，那就要重建路线；如果走的是最短路，但是最短路有多条，可以选择重建和不重建。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=200003;
vector<int>G[N];//正图 
vector<int>rG[N];//反图 
int n,m,k;
int p[N];
int dis[N];
void bfs()
{
	queue<int>q;
	q.push(p[k]);
	while(!q.empty())
	{
		int u=q.front();
		for(auto v:rG[u])//遍历与u相连的点，其到p[k]距离都比v大1
		{
			if(dis[v]>dis[u]+1)
			{
				dis[v]=dis[u]+1;
				q.push(v);
			}
		}
		q.pop();
	}
}
void solve()
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	cin>>n>>m;
	int i;
	for(i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		rG[v].push_back(u);
	}
	cin>>k;
	for(i=1;i<=k;i++) cin>>p[i];
	dis[p[k]]=0;
	bfs();
	int ans_min=0,ans_max=0;
	for(i=1;i<k;i++)
	{
		int ok=0;
		for(auto v:G[p[i]])
		{
			if(dis[v]+1==dis[p[i]])//搜索所有的最短路
			{
				ok++;
			}
		}
		if(dis[p[i+1]]+1!=dis[p[i]])
		{
			ans_min++;
			ans_max++;
		}
		else if(ok>1) ans_max++;
	}
	cout<<ans_min<<' '<<ans_max;
}
int main()
{
	solve();
	return 0;
}