QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#409815#130. Cost Performance FlowKevin5307AC ✓13ms3848kbC++232.0kb2024-05-12 18:48:272024-05-12 18:51:16

Judging History

你现在查看的是最新测评结果

  • [2024-05-12 18:51:16]
  • 评测
  • 测评结果：AC
  • 用时：13ms
  • 内存：3848kb
查看
  • [2024-05-12 18:48:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int a[2005],b[2005],u[2005],c[2005];
vector<int> G[105];
int n,m,s,t;
int dist[2005];
bool inque[2005];
int lst[2005],lste[2005];
pair<__int128,__int128> minFrac(pair<__int128,__int128> a,pair<__int128,__int128> b)
{
	__int128 ga=__gcd(a.first,a.second);
	__int128 gb=__gcd(b.first,b.second);
	a.first/=ga;
	a.second/=ga;
	b.first/=gb;
	b.second/=gb;
	if((__int128)b.first*a.second<(__int128)b.second*a.first)
		return b;
	return a;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i+i-2]>>b[i+i-2]>>u[i+i-2]>>c[i+i-2];
		c[i+i-1]=-c[i+i-2];
		u[i+i-1]=0;
		b[i+i-1]=a[i+i-2];
		a[i+i-1]=b[i+i-2];
		G[a[i+i-2]].push_back(i+i-2);
		G[a[i+i-1]].push_back(i+i-1);
	}
	vector<ll> vec;
	while(true)
	{
		memset(dist,0x3f,sizeof(dist));
		memset(inque,0,sizeof(inque));
		dist[s]=0;
		queue<int> q;
		inque[s]=1;
		q.push(s);
		lst[s]=-1;
		while(!q.empty())
		{
			int x=q.front();
			q.pop();
			inque[x]=0;
			for(auto e:G[x])
				if(u[e]&&dist[x]+c[e]<dist[b[e]])
				{
					dist[b[e]]=dist[x]+c[e];
					lst[b[e]]=x;
					lste[b[e]]=e;
					if(!inque[b[e]])
					{
						inque[b[e]]=1;
						q.push(b[e]);
					}
				}
		}
		if(dist[t]==0x3f3f3f3f) break;
		ll sum=0;
		int cur=t;
		while(cur!=s)
		{
			int e=lste[cur];
			u[e]--;
			u[e^1]++;
			sum+=c[e];
			cur=lst[cur];
		}
		vec.push_back(sum);
	}
	pair<__int128,__int128> ans(accumulate(vec.begin(),vec.end(),0ll)*accumulate(vec.begin(),vec.end(),0ll),1);
	ll sum=0;
	for(int i=0;i<vec.size();i++)
	{
		ll s=sum;
		ll k=vec[i];
		ll t=vec.size()-i;
		ans=minFrac(ans,pair<__int128,__int128>(s*s+t*t,1));
		if(t>s*k&&t-s*k<k*k+1)
			ans=minFrac(ans,pair<__int128,__int128>((__int128)(s+k*t)*(s+k*t)+(__int128)(k*k*t+s*k)*(k*k*t+s*k),(k*k+1)*(k*k+1)));
		sum+=vec[i];
	}
	cout<<(ll)ans.first<<"/"<<(ll)ans.second<<endl;
	return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3728kb

input:

10 90
9 7
1 5 3 3
7 5 1 65
7 9 83 3
10 3 1 29
7 1 1 25
8 2 1 1
3 9 1 6
2 10 39 81
2 8 29 1
6 8 68 81
9 8 7 28
10 6 99 2
7 4 1 13
3 2 2 27
6 5 1 28
3 1 4 40
9 4 42 2
5 10 1 71
1 6 2 5
9 10 44 5
3 10 21 12
8 1 1 26
8 4 44 11
3 5 4 22
2 3 35 1
9 3 10 12
4 1 10 30
2 7 38 14
5 3 59 11
5 9 91 26
8 7 48 50...

output:

430592/13

result:

ok single line: '430592/13'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

10 90
5 4
3 4 16 30
8 5 4 2
4 3 6 11
4 9 5 1
6 1 40 2
9 8 84 3
2 8 64 51
6 8 5 27
10 4 6 8
8 6 51 1
4 5 64 84
8 1 2 19
5 9 21 38
9 4 33 3
6 2 94 2
1 8 39 3
3 7 1 13
8 2 2 33
9 5 8 1
7 9 2 88
8 9 20 7
5 4 1 2
8 4 1 48
7 1 2 88
4 1 2 11
10 9 44 22
7 3 26 7
2 3 43 39
10 6 11 44
4 6 2 2
2 5 60 65
1 5 2 ...

output:

632025/37

result:

ok single line: '632025/37'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

10 90
6 3
5 4 1 1
7 6 1 22
8 10 19 2
9 4 1 1
2 6 23 12
8 5 55 12
10 8 1 56
10 3 67 59
4 2 2 26
9 3 63 43
6 1 14 6
3 7 60 1
9 8 53 91
6 3 2 11
7 8 2 77
5 8 46 3
8 7 1 2
5 7 7 36
5 10 3 2
3 10 43 76
1 4 5 13
5 3 2 1
9 1 90 8
4 5 64 62
10 1 1 3
3 8 5 7
10 6 3 1
4 9 51 1
7 5 79 32
2 5 8 17
9 2 2 7
5 9 4...

output:

3861225/82

result:

ok single line: '3861225/82'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

10 90
8 3
4 10 33 18
4 3 3 1
6 5 95 26
6 10 17 84
4 7 2 53
9 6 1 77
10 3 83 51
2 5 10 58
5 1 75 14
2 4 4 2
10 5 42 4
1 2 35 54
10 4 2 1
3 8 2 50
3 9 24 23
10 1 38 4
3 6 11 24
4 6 3 22
3 2 11 3
2 3 65 1
4 8 77 7
5 10 10 91
1 10 6 6
5 6 8 75
6 3 10 39
6 7 12 12
9 3 3 71
9 5 22 80
6 1 10 8
2 7 31 8
7 4...

output:

169744/5

result:

ok single line: '169744/5'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

10 90
3 8
8 3 49 9
9 2 2 1
3 1 2 12
3 6 1 41
6 4 47 1
9 5 2 1
1 4 2 10
10 7 1 36
3 10 17 15
4 3 10 1
4 6 60 9
1 9 11 1
10 4 17 1
7 3 1 81
9 3 74 1
3 2 1 3
10 9 1 3
2 5 26 2
6 5 87 14
2 10 2 3
6 9 63 6
2 7 1 12
9 4 7 4
4 1 41 1
1 6 1 9
9 1 1 60
5 4 36 1
1 3 1 29
6 2 4 1
8 1 2 24
9 7 39 10
8 2 20 53
9...

output:

717409/17

result:

ok single line: '717409/17'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

10 90
3 7
3 10 45 49
10 3 1 2
4 9 3 81
6 3 16 1
1 5 3 7
5 7 1 1
5 6 21 1
8 5 6 25
4 5 1 22
8 10 91 2
10 1 70 3
10 7 2 91
4 7 1 6
9 5 4 35
1 9 76 8
4 6 2 11
7 2 88 9
4 2 14 53
7 10 73 19
2 9 3 11
8 9 52 31
10 2 9 2
8 7 1 7
6 9 1 48
1 7 15 63
2 8 4 1
10 9 2 19
1 4 36 11
8 1 36 13
4 1 7 8
9 4 1 1
1 3 1...

output:

62500/17

result:

ok single line: '62500/17'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

10 90
4 10
1 8 21 3
2 8 30 63
8 5 13 18
2 4 1 7
10 9 34 46
1 7 25 88
5 2 6 25
5 3 1 45
6 2 1 2
3 7 2 1
1 4 2 1
9 8 2 84
2 7 10 19
4 6 11 23
10 7 4 77
2 9 2 1
5 4 2 3
10 5 56 47
6 4 13 1
3 4 56 1
9 2 6 3
2 1 2 21
5 9 7 1
7 2 6 2
5 8 10 29
1 6 46 6
3 9 3 35
6 5 63 12
9 5 77 30
8 1 1 33
10 8 23 1
4 8 1...

output:

87025/2

result:

ok single line: '87025/2'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

10 90
3 10
5 9 1 6
6 4 2 17
8 7 1 1
5 4 1 28
5 6 13 6
4 1 14 26
5 10 1 5
9 10 4 12
9 8 26 16
3 9 1 7
2 1 1 22
6 9 69 2
2 8 62 7
3 2 7 1
6 1 96 44
10 1 21 90
9 6 13 3
10 7 38 2
6 2 1 26
3 1 2 1
1 7 38 2
3 4 6 11
10 4 3 2
9 2 3 1
8 9 8 26
1 3 25 3
7 8 2 12
8 1 1 67
10 5 28 6
7 3 1 11
4 3 1 36
3 7 1 7
...

output:

133956/17

result:

ok single line: '133956/17'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

10 90
2 1
6 8 10 7
2 7 98 4
4 3 80 78
10 3 93 44
8 5 5 2
1 8 2 23
2 6 27 5
4 9 42 2
5 6 41 4
9 8 1 79
6 5 2 77
3 2 1 27
10 2 68 9
3 8 85 13
1 3 1 2
9 6 99 3
1 5 55 70
7 1 1 47
8 3 2 41
2 10 58 67
8 1 3 54
1 7 12 80
3 9 99 5
6 10 3 2
7 6 6 2
9 2 3 29
6 1 8 4
4 2 65 20
6 7 77 84
7 3 50 27
1 2 36 13
7 ...

output:

202248/41

result:

ok single line: '202248/41'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

10 90
2 7
3 4 2 44
2 1 20 3
2 8 52 40
6 1 74 2
9 3 19 41
6 9 10 31
7 5 7 6
4 3 2 2
10 6 81 10
7 3 37 1
10 5 2 1
4 6 25 1
5 7 4 2
9 6 8 1
10 4 1 1
6 4 2 2
5 1 5 30
1 9 2 8
3 5 12 55
10 3 7 26
7 10 4 11
10 2 74 51
8 7 13 56
8 6 76 41
9 7 9 1
6 3 1 42
3 2 64 14
9 8 49 50
6 2 1 1
10 1 12 1
4 2 3 58
1 7 ...

output:

376712/13

result:

ok single line: '376712/13'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

10 90
7 5
4 6 58 1
8 5 48 47
10 1 1 42
1 8 1 40
10 9 6 25
10 5 2 19
9 8 97 4
7 8 2 3
1 10 16 5
1 3 25 7
5 4 23 1
9 3 3 53
3 6 1 1
10 7 8 23
8 10 95 15
1 7 1 80
9 5 4 6
3 5 1 11
6 9 10 51
9 1 3 23
7 6 7 29
3 7 4 4
5 8 5 3
4 3 11 43
1 2 1 43
2 4 19 21
5 2 10 29
8 6 1 6
8 2 1 53
9 10 54 2
4 9 6 40
3 9 ...

output:

366025/26

result:

ok single line: '366025/26'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

10 90
3 9
1 7 2 1
7 9 9 92
4 2 1 18
6 2 1 14
10 9 9 1
7 10 17 2
9 1 69 10
9 2 4 3
5 3 1 11
10 7 9 10
10 8 15 6
7 5 5 3
4 7 68 31
10 6 20 90
3 8 16 1
2 4 1 23
4 8 2 22
2 9 67 23
4 1 7 1
6 10 4 27
9 4 50 8
1 9 33 1
5 4 5 1
6 4 58 1
3 2 2 10
5 2 79 3
6 9 20 48
4 5 65 41
5 10 76 3
3 4 3 15
6 7 10 1
1 8 ...

output:

558009/17

result:

ok single line: '558009/17'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

10 90
9 8
6 8 15 6
8 4 19 3
4 5 69 6
9 3 10 8
10 8 32 6
2 3 57 67
3 7 12 35
3 4 7 10
2 1 34 3
9 2 8 1
6 7 1 10
6 10 77 5
8 1 65 3
1 4 25 4
6 2 91 1
10 4 18 1
9 8 7 56
10 3 20 4
9 7 1 37
3 6 27 3
2 9 21 23
6 3 18 13
7 6 5 1
7 9 1 36
4 2 31 9
8 5 23 66
4 3 7 64
4 7 4 18
1 5 1 9
6 9 4 24
3 10 24 47
10 ...

output:

89557/2

result:

ok single line: '89557/2'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

10 90
3 10
8 7 7 12
5 9 2 3
6 5 9 49
5 2 3 33
2 6 51 10
2 5 11 1
1 5 6 93
3 1 2 5
5 6 6 4
4 10 38 74
6 10 7 1
2 10 4 10
4 7 7 23
10 5 38 10
1 2 11 2
9 5 24 12
6 3 8 3
7 1 2 2
9 7 12 17
6 9 4 12
7 6 8 43
5 4 93 37
5 8 7 1
8 9 59 66
5 7 6 10
10 4 42 14
6 4 52 2
2 3 5 4
8 3 80 14
4 9 4 2
1 9 41 17
10 1...

output:

847602/25

result:

ok single line: '847602/25'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

10 90
5 2
3 2 2 80
10 8 6 9
3 5 12 3
8 1 34 2
6 9 2 35
1 7 11 2
2 9 24 52
2 3 19 1
8 7 3 5
4 8 93 33
3 6 4 5
10 5 43 38
10 9 87 1
2 1 7 1
8 2 21 1
2 6 28 11
10 4 13 44
9 4 25 1
2 5 8 43
6 5 37 5
2 7 17 1
8 3 3 9
4 3 2 18
10 1 10 4
7 5 8 3
8 10 25 4
5 9 4 1
9 1 3 15
1 2 28 6
8 4 31 2
1 10 56 64
1 9 2...

output:

14989/1

result:

ok single line: '14989/1'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

10 90
9 8
4 1 1 81
4 6 2 4
7 8 9 2
4 5 5 1
7 4 23 2
3 7 23 3
3 8 4 30
1 3 3 32
10 9 5 5
7 3 38 2
8 10 53 86
7 2 1 20
4 10 20 1
2 6 2 4
8 4 68 6
7 9 69 29
3 5 9 1
9 3 88 9
7 1 41 78
3 6 17 1
6 9 33 10
5 7 30 2
3 1 6 1
10 2 32 15
6 8 10 9
7 5 67 10
8 9 2 3
6 5 5 84
6 7 28 1
2 5 9 54
1 7 1 8
5 2 3 74
2...

output:

205209/10

result:

ok single line: '205209/10'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

10 90
10 6
8 1 14 29
4 5 5 81
5 10 60 31
10 2 2 89
8 6 19 7
9 4 34 15
8 5 70 16
5 8 10 1
8 4 97 8
1 7 1 31
6 4 2 56
2 1 8 56
6 5 8 39
4 1 5 9
6 3 18 9
1 2 8 97
7 2 84 1
1 9 15 25
7 1 16 13
6 2 3 21
2 6 5 1
4 2 3 10
3 5 56 3
9 7 11 2
10 5 55 6
2 5 15 33
9 10 21 14
5 2 3 2
8 2 4 3
4 7 2 25
7 10 11 19
...

output:

501264/37

result:

ok single line: '501264/37'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

10 90
10 9
5 6 3 3
9 6 3 5
8 1 2 2
8 10 2 1
8 9 14 12
2 3 20 8
2 8 3 38
5 1 37 6
4 9 22 1
1 4 30 33
7 5 7 11
2 7 28 3
4 1 93 6
9 5 4 25
8 7 1 57
7 4 28 25
2 1 3 71
9 10 23 7
1 9 33 2
5 10 29 29
6 3 3 49
7 1 2 1
8 6 1 1
8 2 1 19
10 1 56 2
1 10 3 78
7 3 2 3
3 1 2 8
4 7 26 4
3 8 41 4
6 1 1 67
9 1 10 18...

output:

504100/17

result:

ok single line: '504100/17'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

10 90
3 2
6 8 10 5
5 2 36 4
10 5 35 22
3 7 4 26
6 10 6 19
7 8 3 3
8 7 2 1
9 4 3 4
5 6 9 9
2 7 4 1
2 6 3 94
9 5 1 4
2 3 32 5
4 5 7 2
9 2 4 11
10 9 32 4
2 8 7 86
7 6 3 26
10 4 18 1
10 7 23 4
1 8 30 12
10 8 4 34
5 10 1 55
8 9 2 1
4 1 28 52
8 6 31 42
3 1 1 7
7 5 8 25
3 4 10 4
7 1 1 3
1 2 6 3
1 6 57 9
10...

output:

567009/10

result:

ok single line: '567009/10'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

10 90
5 10
10 2 10 33
10 8 2 15
9 6 21 31
4 2 2 52
9 7 2 31
2 3 5 20
3 5 18 39
4 1 30 5
5 10 1 9
1 9 16 1
6 10 1 4
2 8 1 1
1 6 6 25
4 7 45 61
8 3 5 1
7 1 5 11
8 10 42 6
5 9 8 2
8 6 4 2
7 9 4 1
8 7 2 2
1 4 1 2
9 5 6 5
5 4 1 3
7 10 50 56
3 7 1 84
8 9 4 1
2 6 28 8
7 5 5 1
6 5 2 82
2 5 7 74
3 6 11 1
4 3...

output:

734449/50

result:

ok single line: '734449/50'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

22 100
5 3
12 1 2 2
7 13 32 3
5 10 28 2
16 22 4 1
5 21 22 46
7 4 1 3
11 8 20 17
12 13 11 42
14 4 6 60
5 14 2 23
6 13 76 5
6 2 5 35
5 7 10 36
5 15 13 2
2 3 1 10
7 18 1 1
11 1 5 15
10 1 7 15
12 19 36 30
15 4 86 46
7 19 10 1
5 9 3 17
16 19 5 54
10 2 34 52
12 18 10 1
11 20 1 1
12 4 12 6
15 17 1 5
9 1 44...

output:

1836025/82

result:

ok single line: '1836025/82'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

22 100
14 3
15 16 1 3
10 22 35 16
8 20 3 15
7 3 48 29
15 6 10 9
9 2 65 5
12 17 22 8
19 1 30 5
4 6 39 1
11 22 2 15
5 22 2 44
5 7 3 2
10 20 1 80
12 18 17 1
9 18 1 41
9 6 12 2
20 3 35 1
10 17 4 98
12 20 3 7
14 4 94 2
21 18 1 7
2 3 4 23
19 6 38 9
8 16 78 4
14 12 2 82
10 7 37 23
5 2 72 6
4 13 6 27
15 7 1...

output:

868624/17

result:

ok single line: '868624/17'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

22 100
6 21
22 12 1 59
1 21 8 26
17 8 20 1
8 21 7 16
15 21 2 1
4 12 19 12
14 21 1 25
20 8 13 1
11 21 22 89
3 8 16 1
3 12 7 8
18 14 13 1
17 12 18 82
4 10 1 1
20 19 12 15
17 11 1 91
17 15 30 69
10 21 47 2
13 14 41 26
2 8 6 19
6 2 2 40
17 19 5 4
13 9 30 60
22 11 7 5
6 16 63 19
12 21 7 4
19 21 32 82
16 ...

output:

417698/13

result:

ok single line: '417698/13'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

22 100
19 3
5 3 45 40
7 21 1 67
1 22 3 3
19 16 51 6
4 15 20 3
6 3 3 4
18 21 23 3
14 5 7 1
1 13 7 17
12 8 4 10
1 5 10 91
12 6 3 16
18 10 21 8
16 20 4 9
14 15 87 53
7 6 14 1
1 8 3 1
14 8 10 6
12 10 9 4
11 20 97 26
14 10 1 1
12 21 1 27
14 6 7 3
1 15 58 1
13 3 60 2
4 13 3 41
4 22 18 1
2 22 1 1
11 10 25 ...

output:

2961841/82

result:

ok single line: '2961841/82'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

22 100
13 7
15 9 41 4
13 8 98 11
20 5 7 9
8 1 50 1
3 5 1 9
4 19 31 15
13 16 17 85
20 1 1 3
13 6 6 7
21 1 69 3
17 9 5 10
10 7 14 2
13 11 21 32
4 12 67 19
6 2 17 7
11 1 26 3
15 10 1 21
16 2 1 27
17 2 76 6
13 17 3 30
8 19 4 10
4 22 2 31
21 5 1 1
22 7 74 97
20 14 33 22
21 10 62 1
15 22 36 7
17 22 36 21
...

output:

4177936/197

result:

ok single line: '4177936/197'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

22 100
3 16
3 15 6 1
14 5 1 46
9 4 99 30
17 13 63 5
17 21 28 19
11 21 1 7
11 13 1 1
11 2 9 2
14 1 2 1
3 17 1 87
15 21 8 2
3 11 8 17
15 7 7 4
9 10 12 18
11 20 56 2
18 2 3 41
14 13 2 4
18 21 1 1
3 19 1 2
22 6 3 11
14 7 26 2
8 2 2 36
19 10 3 3
12 7 1 85
3 18 4 68
12 2 15 2
22 13 10 1
20 16 19 8
14 10 5...

output:

156800/13

result:

ok single line: '156800/13'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

22 100
16 19
10 14 3 41
13 3 5 23
2 1 12 22
17 21 2 27
17 6 57 44
4 1 15 1
17 3 5 54
18 22 21 14
11 3 4 93
5 9 27 2
16 4 7 57
12 3 3 33
11 6 15 12
8 1 18 1
17 15 27 1
10 21 1 54
2 3 64 60
13 6 12 70
16 2 3 76
21 19 32 3
2 9 4 2
12 1 36 81
11 15 1 22
4 22 7 10
9 19 11 55
1 19 2 73
12 22 3 21
18 21 13...

output:

311364/37

result:

ok single line: '311364/37'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

22 100
9 6
14 4 1 72
15 10 8 9
11 17 46 17
1 3 9 32
11 7 4 21
14 2 29 10
13 4 16 7
19 8 95 45
2 6 4 71
14 21 22 21
9 12 24 20
4 6 21 16
11 3 2 16
14 8 3 3
1 8 2 4
15 7 10 11
9 18 99 54
19 3 14 95
12 17 1 39
11 22 5 1
11 2 61 45
11 8 1 48
5 17 4 50
13 22 5 3
19 4 11 3
22 6 14 13
13 7 1 2
1 17 8 51
19...

output:

1185921/82

result:

ok single line: '1185921/82'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

22 100
6 20
5 21 1 17
17 13 53 2
17 8 39 9
5 22 2 8
18 21 1 4
2 16 32 9
1 9 26 10
18 4 32 76
17 4 24 2
18 9 1 1
7 13 64 1
6 10 76 9
7 15 6 46
1 4 27 1
2 9 66 31
10 16 2 11
5 16 1 2
18 22 16 1
12 13 8 9
10 4 6 6
19 15 37 99
19 9 10 1
6 14 6 5
1 11 73 1
19 13 4 2
14 8 12 1
18 8 67 9
7 21 11 1
1 22 34 ...

output:

958441/50

result:

ok single line: '958441/50'

Test #30:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

22 100
13 18
10 18 44 4
3 8 56 5
22 6 16 79
11 10 6 42
13 15 26 1
20 9 2 6
13 1 2 22
14 17 27 33
6 18 3 33
19 18 43 20
15 6 1 43
11 19 1 60
21 5 1 27
20 6 76 9
7 5 1 3
13 20 9 2
15 16 2 92
1 5 4 19
5 18 87 26
7 16 67 1
1 6 80 26
3 19 99 41
16 18 34 19
11 9 17 17
15 9 7 2
20 17 9 8
11 12 37 1
15 19 4...

output:

288800/13

result:

ok single line: '288800/13'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

22 100
14 11
5 1 2 9
3 18 4 14
3 1 13 15
5 19 20 4
14 4 1 3
5 6 1 2
5 15 4 53
2 21 29 12
17 18 7 10
3 6 6 4
20 15 1 60
9 13 1 21
14 16 11 8
6 11 1 11
14 3 60 59
16 15 15 48
10 22 12 10
3 12 2 76
16 19 65 1
14 8 2 96
17 1 1 1
10 12 75 5
9 19 19 5
3 21 72 90
17 13 12 7
4 6 31 7
16 21 6 2
2 18 36 3
2 1...

output:

4571044/101

result:

ok single line: '4571044/101'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

22 100
17 16
20 13 3 7
9 5 7 1
7 3 1 29
15 11 10 1
7 14 8 4
15 6 1 43
20 6 2 12
15 4 4 95
12 14 8 1
10 22 1 1
5 16 11 1
14 16 27 1
17 8 2 1
9 3 21 17
10 21 1 49
17 10 6 8
9 13 4 1
8 5 1 67
12 3 1 63
2 22 9 49
21 16 1 4
19 16 48 91
8 11 95 10
17 1 31 12
12 5 2 4
2 19 67 1
7 11 5 1
1 13 14 1
3 16 1 51...

output:

154449/10

result:

ok single line: '154449/10'

Test #33:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

22 100
12 19
8 9 4 27
18 5 6 8
3 20 43 4
6 7 11 4
3 13 32 37
1 11 1 55
10 7 4 11
14 11 13 19
17 21 7 57
21 19 3 1
17 11 83 40
12 10 47 39
3 5 4 60
2 15 7 45
8 5 2 25
12 14 10 9
17 5 41 13
18 4 1 12
1 16 15 67
18 15 3 11
6 21 49 32
22 21 1 4
2 4 5 11
14 15 2 4
3 9 1 2
16 19 10 9
12 1 3 6
1 15 90 3
6 ...

output:

609961/26

result:

ok single line: '609961/26'

Test #34:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

22 100
14 9
2 9 25 8
22 3 2 36
20 21 1 2
21 9 6 1
20 2 1 8
13 18 23 78
14 13 1 37
17 21 30 1
11 1 14 99
5 15 5 5
14 12 10 1
4 21 15 21
12 2 14 59
22 10 1 4
12 3 98 2
3 9 11 7
12 8 94 3
13 15 66 1
17 1 97 2
7 16 3 11
20 1 92 36
7 2 1 86
5 10 39 1
11 8 4 24
20 10 10 97
5 8 92 7
14 17 16 2
4 15 37 1
12...

output:

192721/17

result:

ok single line: '192721/17'

Test #35:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

22 100
1 4
20 2 26 96
5 7 31 2
17 12 50 1
3 7 26 4
5 6 4 63
13 4 17 63
1 21 32 63
18 7 2 6
17 15 1 1
1 18 1 6
6 4 39 22
18 12 4 3
1 19 91 1
1 5 40 10
19 7 3 1
20 8 10 6
3 16 7 8
19 13 8 42
1 17 53 12
19 12 10 91
22 10 5 47
17 14 5 8
22 14 4 20
20 6 70 26
11 10 7 2
22 16 8 2
12 4 13 35
11 7 1 2
9 15 ...

output:

13205956/145

result:

ok single line: '13205956/145'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

22 100
8 21
4 20 53 11
18 16 1 1
7 16 1 62
17 20 10 15
17 15 7 3
19 21 1 8
1 21 87 2
5 1 67 5
22 15 2 79
18 2 3 1
5 6 22 84
5 19 9 98
7 20 29 6
17 3 1 2
8 10 18 2
9 15 1 4
18 19 15 3
4 15 2 8
11 16 16 17
22 2 7 31
22 16 10 14
17 19 13 7
11 2 2 80
4 6 12 5
8 14 93 6
22 3 8 1
14 13 2 3
4 1 70 22
7 3 3...

output:

571536/37

result:

ok single line: '571536/37'

Test #37:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

22 100
7 11
16 19 1 1
15 10 12 2
7 15 28 34
17 19 15 13
5 1 3 20
7 5 4 6
21 11 94 12
18 8 7 3
16 3 20 26
7 20 8 32
20 21 6 25
14 21 93 27
19 11 69 2
2 19 11 5
12 13 15 29
14 4 1 96
5 9 23 43
17 3 17 61
15 3 8 9
20 13 33 2
15 13 3 55
2 1 25 2
18 3 12 1
7 16 6 2
7 17 5 43
6 22 2 30
9 11 27 99
18 1 4 3...

output:

552049/26

result:

ok single line: '552049/26'

Test #38:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

22 100
2 15
9 7 31 51
14 4 1 55
18 5 1 1
20 17 27 61
1 16 2 3
14 11 2 3
18 22 7 1
20 5 17 1
13 22 2 1
2 21 53 18
19 10 2 3
2 13 4 36
13 10 6 36
18 16 4 18
11 15 99 87
20 7 3 26
21 11 14 4
5 15 13 1
19 7 1 43
20 4 15 3
19 8 30 5
9 8 2 1
21 6 2 75
20 6 3 95
2 9 7 46
12 6 10 51
19 22 2 46
1 8 63 98
13 ...

output:

4618201/122

result:

ok single line: '4618201/122'

Test #39:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

22 100
13 19
2 7 29 1
20 18 24 12
6 1 2 48
4 17 40 1
17 19 1 28
8 16 18 38
8 21 3 8
8 17 40 1
2 21 5 16
2 22 16 2
13 6 63 61
16 19 2 33
11 16 1 12
13 4 10 73
6 9 91 14
6 22 86 49
18 19 2 1
3 5 15 4
12 16 34 62
10 5 2 9
6 17 19 50
20 17 5 8
20 22 2 2
2 18 6 20
13 10 13 31
11 17 48 2
6 16 1 4
11 15 1 ...

output:

491401/82

result:

ok single line: '491401/82'

Test #40:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

22 100
7 15
21 17 15 15
10 14 3 86
8 14 6 47
10 17 1 4
10 4 8 1
16 13 31 1
21 6 86 3
1 14 5 17
7 8 1 4
5 11 5 1
7 10 12 1
3 2 17 2
18 4 77 36
18 17 8 1
18 20 10 2
21 13 38 17
1 2 21 5
1 22 9 3
16 4 66 23
18 2 10 80
1 17 2 24
19 22 38 84
8 22 42 1
8 6 1 6
1 12 3 5
16 14 74 10
21 12 87 20
7 5 45 17
3 ...

output:

1968409/50

result:

ok single line: '1968409/50'

Test #41:

score: 0
Accepted
time: 2ms
memory: 3804kb

input:

100 1000
28 55
73 25 7 12
24 27 2 94
54 60 2 4
23 11 8 2
26 44 77 45
20 86 1 47
2 76 18 2
9 51 58 47
54 2 3 79
58 70 4 2
40 66 6 21
55 6 30 3
64 15 5 2
5 40 22 4
84 69 15 1
88 25 7 11
63 69 77 10
16 18 71 52
45 19 2 33
8 89 55 38
32 47 19 7
33 83 6 3
35 39 7 1
92 21 1 24
90 15 6 1
13 19 5 65
83 54 1...

output:

837225/37

result:

ok single line: '837225/37'

Test #42:

score: 0
Accepted
time: 3ms
memory: 3592kb

input:

100 1000
66 36
8 31 14 8
57 31 89 36
17 10 33 2
60 52 2 24
16 65 25 21
100 30 7 19
56 30 17 3
24 15 2 15
97 67 1 2
7 14 8 91
25 1 9 13
75 17 17 80
89 68 44 91
31 59 26 74
2 9 7 44
73 74 1 41
20 32 7 18
26 30 48 2
53 44 4 17
79 95 24 25
60 35 1 5
67 21 62 1
3 93 1 2
42 5 18 3
70 77 13 12
50 65 12 5
3...

output:

749088/41

result:

ok single line: '749088/41'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

100 1000
61 35
54 66 8 8
74 76 1 29
5 21 4 38
10 51 18 4
54 15 99 28
7 71 3 23
33 60 1 1
53 49 1 4
69 37 86 1
58 27 24 22
33 53 4 16
52 8 6 2
65 7 13 27
96 62 86 23
79 14 3 2
41 28 29 6
81 100 16 1
23 52 3 30
99 66 5 2
27 65 27 57
51 40 27 2
74 39 1 4
26 42 1 27
81 91 30 58
83 34 1 4
71 84 5 38
24 6...

output:

15925/2

result:

ok single line: '15925/2'

Test #44:

score: 0
Accepted
time: 3ms
memory: 3624kb

input:

100 1000
93 16
16 14 1 1
86 42 78 6
62 68 1 4
76 54 92 1
3 63 6 25
87 98 25 30
78 7 2 8
14 54 18 1
96 62 24 13
45 38 12 1
9 84 1 5
96 12 74 15
15 17 2 2
31 41 21 79
29 42 12 74
22 66 16 2
63 97 7 65
72 100 45 1
8 46 27 18
47 68 4 2
21 42 12 4
13 20 3 1
47 74 1 13
11 40 66 3
3 8 7 3
50 11 6 5
5 89 26...

output:

75809/2

result:

ok single line: '75809/2'

Test #45:

score: 0
Accepted
time: 3ms
memory: 3576kb

input:

100 1000
86 45
22 71 2 13
5 60 7 36
37 62 1 1
82 23 66 1
88 99 37 1
73 75 11 4
83 15 18 10
70 86 97 6
8 87 7 1
96 99 4 67
90 51 77 2
55 99 24 1
63 69 13 5
86 23 11 22
68 34 1 27
50 52 21 97
6 14 1 13
55 100 4 6
82 72 27 13
2 90 31 3
69 1 1 70
58 15 34 6
21 74 97 6
86 26 3 2
46 78 1 12
6 59 3 50
66 3...

output:

13306/1

result:

ok single line: '13306/1'

Test #46:

score: 0
Accepted
time: 3ms
memory: 3624kb

input:

100 1000
1 54
63 17 6 2
85 8 93 12
65 11 1 10
19 63 6 10
81 58 11 18
27 85 9 6
87 24 16 12
23 100 1 16
3 44 12 24
35 58 17 16
46 76 4 45
43 91 31 6
26 8 4 1
18 8 33 2
42 13 9 6
39 43 4 6
66 80 9 5
29 96 1 13
60 82 3 4
70 44 2 44
30 80 20 68
76 17 1 3
3 77 2 3
38 84 3 10
60 92 12 22
29 97 68 1
92 90 ...

output:

2157961/101

result:

ok single line: '2157961/101'

Test #47:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

100 1000
2 86
70 28 40 13
5 27 36 14
29 9 60 47
10 18 6 17
86 6 70 44
45 37 17 3
73 26 5 95
22 59 4 1
56 99 8 16
55 2 66 21
78 75 3 9
70 82 23 4
50 5 7 3
26 97 2 2
64 93 8 14
43 14 1 1
32 26 3 10
65 18 43 11
25 32 35 67
19 47 78 13
77 25 54 33
67 43 2 10
61 52 23 13
82 46 1 7
93 32 46 3
100 87 16 4
...

output:

1087849/50

result:

ok single line: '1087849/50'

Test #48:

score: 0
Accepted
time: 4ms
memory: 3832kb

input:

100 1000
53 36
93 89 1 3
84 36 1 23
70 55 1 91
69 91 3 3
85 59 1 25
83 55 23 37
65 85 25 83
63 38 4 3
25 75 92 7
44 17 64 30
70 57 4 2
27 26 4 45
44 35 4 22
21 70 4 41
21 40 11 8
52 44 4 1
90 71 17 26
85 89 2 2
2 17 67 11
83 12 47 13
80 21 24 5
78 49 22 37
44 8 8 75
51 73 18 4
72 85 25 1
11 14 23 68...

output:

2044900/101

result:

ok single line: '2044900/101'

Test #49:

score: 0
Accepted
time: 3ms
memory: 3552kb

input:

100 1000
46 75
69 5 22 44
97 38 1 98
36 40 2 1
10 11 2 2
97 23 5 2
76 88 39 36
22 43 4 1
22 90 6 5
88 97 2 5
18 22 1 31
65 85 13 14
72 91 93 18
98 36 21 2
49 31 11 25
26 49 7 10
61 5 9 11
37 35 1 64
51 12 25 3
80 68 3 6
30 13 1 14
85 20 50 1
100 64 7 16
60 21 8 2
77 39 11 2
51 53 2 58
64 76 1 2
98 4...

output:

2528100/101

result:

ok single line: '2528100/101'

Test #50:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

100 1000
76 3
52 93 1 41
93 45 2 2
93 46 55 26
77 23 11 85
34 70 7 9
64 12 10 31
29 24 2 98
15 27 2 2
41 78 2 29
25 68 5 4
84 10 17 86
88 91 10 2
38 15 19 21
54 23 7 45
95 86 3 2
91 89 56 23
65 41 5 80
100 26 2 1
98 91 2 8
5 76 17 70
9 67 80 92
1 21 81 3
55 46 11 1
19 35 4 1
89 49 93 18
53 1 19 3
60...

output:

6500/1

result:

ok single line: '6500/1'

Test #51:

score: 0
Accepted
time: 2ms
memory: 3808kb

input:

100 1000
97 74
34 87 1 38
43 29 6 32
59 49 24 4
21 53 70 14
38 33 6 27
12 13 1 2
26 36 14 1
37 96 1 14
48 37 6 5
7 72 7 3
47 1 1 3
30 41 6 21
54 80 3 10
34 68 10 10
100 36 23 5
26 94 1 11
42 85 2 23
29 33 65 11
8 16 2 8
54 35 2 2
65 63 99 14
42 66 1 17
97 22 65 5
10 7 9 15
76 44 66 7
15 78 1 1
17 79...

output:

923521/65

result:

ok single line: '923521/65'

Test #52:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

100 1000
20 27
70 56 3 62
4 67 1 1
13 79 16 13
21 13 1 72
70 44 30 3
52 53 1 32
47 25 80 31
5 99 44 35
41 53 9 50
42 40 61 22
37 49 14 1
98 14 12 9
72 36 2 2
8 89 8 10
84 41 49 38
62 15 34 6
91 48 73 29
42 85 8 19
97 88 12 2
10 44 1 90
37 36 2 80
22 66 5 1
73 90 1 8
74 60 1 4
94 3 1 3
44 66 39 7
15 ...

output:

1567504/37

result:

ok single line: '1567504/37'

Test #53:

score: 0
Accepted
time: 2ms
memory: 3600kb

input:

100 1000
18 60
48 65 72 4
23 22 32 88
93 79 22 8
34 32 69 87
65 37 8 3
31 66 5 7
53 75 4 2
58 94 14 1
67 60 3 87
26 53 43 2
75 18 11 36
17 49 9 16
32 85 4 7
50 3 81 3
59 70 1 5
48 67 47 21
75 23 58 19
56 95 96 7
48 28 3 7
3 89 1 22
41 29 6 17
77 33 2 2
80 16 14 50
59 47 7 22
68 22 84 40
98 37 3 6
30...

output:

366025/17

result:

ok single line: '366025/17'

Test #54:

score: 0
Accepted
time: 4ms
memory: 3628kb

input:

100 1000
52 82
97 8 16 8
18 26 1 1
11 52 26 12
38 80 53 31
92 57 3 36
29 3 28 6
43 93 2 2
73 30 27 20
6 62 17 2
17 64 20 1
97 20 5 3
23 62 2 27
27 52 32 11
53 58 2 2
92 54 1 8
93 45 17 35
40 17 2 8
87 27 5 78
7 70 14 27
83 54 2 6
45 30 28 66
67 4 1 1
92 87 31 2
67 77 51 22
68 57 52 38
16 32 79 4
86 ...

output:

2550409/82

result:

ok single line: '2550409/82'

Test #55:

score: 0
Accepted
time: 6ms
memory: 3816kb

input:

100 1000
27 60
58 43 5 22
69 97 19 28
54 12 3 1
15 7 18 1
43 74 27 49
40 60 9 31
25 20 1 1
86 17 23 4
44 17 12 4
53 95 12 56
56 43 82 10
93 47 34 36
100 7 40 1
68 20 29 98
17 22 3 6
62 45 25 24
98 42 11 16
60 67 38 2
67 60 96 2
26 46 1 30
81 75 14 2
86 18 1 19
12 76 26 76
82 58 8 1
96 30 66 50
57 52...

output:

5837056/65

result:

ok single line: '5837056/65'

Test #56:

score: 0
Accepted
time: 3ms
memory: 3808kb

input:

100 1000
46 18
89 85 1 5
69 84 50 2
79 13 3 1
27 73 1 3
91 95 1 84
11 98 1 1
5 33 2 1
43 87 2 29
84 94 15 4
57 65 1 40
67 78 1 10
17 64 40 3
3 20 72 83
69 10 1 61
16 35 1 41
69 73 46 8
78 51 4 7
32 33 2 1
28 55 3 27
54 85 80 36
51 45 5 9
100 63 4 4
26 1 62 42
12 13 1 10
33 35 17 8
12 26 92 3
13 52 4...

output:

252050/13

result:

ok single line: '252050/13'

Test #57:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

100 1000
70 12
39 64 13 5
97 96 1 20
58 99 2 1
70 4 1 2
53 29 12 3
54 53 2 12
11 3 18 56
16 2 1 9
69 16 12 1
21 8 15 12
76 38 32 83
18 31 1 7
61 23 8 1
15 13 5 21
21 40 2 1
3 55 81 16
33 52 72 32
84 82 30 1
30 72 1 1
74 45 2 27
33 54 26 4
15 34 5 52
89 42 15 1
66 37 7 23
8 17 15 43
59 51 1 1
24 75 1...

output:

41616/37

result:

ok single line: '41616/37'

Test #58:

score: 0
Accepted
time: 3ms
memory: 3808kb

input:

100 1000
89 68
29 91 99 16
55 47 26 4
81 53 6 1
93 36 6 92
71 89 3 3
57 33 95 11
86 85 1 50
77 30 8 67
6 23 68 41
10 27 1 61
37 55 26 1
82 57 1 6
49 71 6 2
85 95 1 1
91 43 38 1
36 85 4 9
8 96 3 12
38 70 1 55
19 100 30 10
52 28 65 1
59 24 13 3
93 54 1 25
23 96 3 2
65 57 11 31
35 60 33 13
28 48 9 7
11...

output:

1071225/37

result:

ok single line: '1071225/37'

Test #59:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

100 1000
16 75
44 20 63 73
55 53 1 2
93 65 2 9
27 3 1 82
37 45 69 61
9 37 5 10
14 77 21 2
88 65 14 99
91 11 58 1
42 86 6 2
63 36 1 1
56 1 23 9
83 77 47 60
94 14 2 9
67 84 16 11
26 1 4 1
58 21 39 2
31 46 1 9
92 44 17 4
62 98 1 64
91 89 6 16
91 99 24 13
61 14 6 4
75 12 3 36
94 60 1 21
22 97 1 1
68 1 2...

output:

3048516/325

result:

ok single line: '3048516/325'

Test #60:

score: 0
Accepted
time: 5ms
memory: 3756kb

input:

100 1000
43 33
16 55 3 1
8 86 2 68
93 82 6 34
5 82 52 6
18 7 22 8
12 27 42 28
21 29 1 5
87 5 68 8
67 44 24 12
42 7 7 51
68 91 51 11
10 28 1 10
56 100 23 99
40 30 72 6
26 25 17 9
43 17 18 84
76 51 4 8
68 37 89 50
51 37 10 3
79 72 25 3
82 3 49 4
68 34 1 8
42 34 29 74
42 72 18 37
50 4 10 1
59 27 8 11
5...

output:

3936256/101

result:

ok single line: '3936256/101'

Test #61:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

100 100
98 69
96 69 1 2
98 47 2 27
60 69 68 2
98 23 7 22
98 6 90 4
98 7 83 1
98 26 72 3
70 69 2 87
98 65 22 6
68 69 1 27
77 69 5 34
98 92 11 1
42 69 10 39
63 69 4 30
55 69 86 99
98 97 16 90
32 69 2 3
98 33 8 1
13 69 1 2
98 37 28 25
98 43 92 93
22 69 33 78
98 28 9 2
98 53 12 2
59 14 12 25
98 88 24 3
...

output:

208080/2081

result:

ok single line: '208080/2081'

Test #62:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

100 100
69 66
69 11 15 22
28 66 2 29
69 42 7 25
24 66 5 63
57 66 28 29
22 66 18 19
69 84 1 31
69 59 15 3
63 66 67 24
45 66 4 4
69 41 10 22
96 66 11 19
35 66 12 56
69 85 6 39
69 88 64 28
69 7 32 70
69 4 4 94
69 1 21 27
69 54 80 3
43 66 28 72
94 66 33 2
44 66 69 15
30 66 11 1
69 26 6 40
52 66 82 9
69 ...

output:

52488/3281

result:

ok single line: '52488/3281'

Test #63:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

100 100
82 49
82 12 1 1
82 71 2 67
82 87 7 28
82 65 18 23
82 53 65 71
82 92 36 40
68 49 37 1
39 49 25 1
82 67 10 10
44 49 7 6
82 85 6 1
42 49 62 13
75 49 1 8
82 51 79 3
82 64 27 2
82 91 30 2
82 31 43 48
82 15 2 62
76 49 12 3
82 99 28 20
54 49 4 1
82 95 3 2
84 49 3 8
28 49 20 14
16 49 1 7
22 49 1 63
...

output:

9216/145

result:

ok single line: '9216/145'

Test #64:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

100 100
18 5
18 29 26 33
41 5 8 80
18 68 29 2
18 6 81 8
18 100 8 31
18 85 49 18
38 5 45 12
47 5 60 53
52 5 20 50
18 28 3 14
21 5 38 8
49 5 5 3
7 5 94 12
18 72 6 64
18 93 70 12
20 5 2 8
18 40 2 3
18 59 2 11
42 5 11 46
37 5 2 23
18 31 66 1
18 71 26 1
3 5 44 10
18 9 40 14
61 5 13 64
67 5 3 46
18 4 14 6...

output:

53361/1090

result:

ok single line: '53361/1090'

Test #65:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

100 100
40 58
30 58 13 8
40 24 1 3
40 55 33 29
40 98 63 12
40 28 3 1
40 8 11 5
40 54 56 71
48 58 54 41
15 58 8 8
84 58 64 2
40 65 5 19
62 58 19 18
91 58 78 95
40 49 5 3
28 90 32 1
27 58 96 20
36 58 2 8
40 83 63 15
22 58 6 97
13 58 10 33
40 99 2 76
40 11 28 1
40 32 67 1
73 58 1 2
89 58 86 15
100 58 5...

output:

7744/485

result:

ok single line: '7744/485'

Test #66:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

100 100
100 18
100 74 5 3
100 2 1 1
59 18 10 35
15 18 3 10
26 18 50 25
100 70 7 8
32 91 14 2
100 85 77 1
100 19 2 2
100 7 6 10
36 18 3 6
100 33 1 5
100 42 30 4
73 91 20 2
27 18 32 20
100 77 27 31
97 18 18 5
62 18 2 8
100 31 4 20
100 39 9 2
100 99 22 94
11 18 11 4
47 18 23 85
100 82 10 4
100 14 6 1
1...

output:

5290/53

result:

ok single line: '5290/53'

Test #67:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

100 100
86 25
86 40 3 5
75 25 9 1
86 42 70 7
86 21 48 4
44 25 4 45
69 25 2 19
30 25 1 5
86 17 1 57
32 25 16 4
86 91 46 35
86 64 11 2
85 25 61 78
12 25 1 6
86 97 9 2
86 55 4 2
68 25 20 5
94 30 1 33
71 25 23 2
86 2 2 25
86 33 54 3
23 25 6 46
15 25 45 9
13 25 5 1
86 16 21 51
22 25 17 63
86 47 3 4
86 60...

output:

29241/3250

result:

ok single line: '29241/3250'

Test #68:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

100 100
5 40
5 61 2 2
5 73 7 4
97 40 2 11
85 40 75 50
5 37 76 8
16 40 43 2
28 40 7 1
5 92 16 1
94 40 4 61
5 70 3 43
57 40 2 1
5 72 68 32
5 64 30 3
5 12 15 11
78 40 18 4
2 40 2 85
26 40 6 14
5 50 10 4
3 40 9 82
60 40 6 21
5 46 1 3
5 35 36 1
5 47 16 8
44 40 70 50
5 88 1 7
5 100 3 41
5 10 19 3
38 40 1 ...

output:

144/17

result:

ok single line: '144/17'

Test #69:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

100 100
32 15
44 15 38 17
32 50 8 22
21 15 64 55
49 15 6 25
32 73 60 28
70 15 67 72
32 47 3 22
32 67 39 4
32 38 1 69
32 51 17 10
77 15 9 13
32 28 13 60
32 63 40 21
32 98 8 12
100 15 27 92
32 31 68 2
32 92 20 84
32 16 1 72
99 15 17 41
91 15 1 22
32 26 53 3
54 15 1 16
68 15 5 4
3 15 31 14
32 69 19 5
3...

output:

82944/1025

result:

ok single line: '82944/1025'

Test #70:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

100 100
28 90
22 90 2 5
44 90 1 62
28 31 3 38
53 90 1 14
28 10 12 3
11 90 17 36
93 90 33 1
5 90 25 55
70 90 2 1
57 90 1 8
28 55 63 1
51 90 2 1
28 26 52 1
28 3 3 6
15 90 4 4
85 79 38 28
60 90 66 4
47 90 28 6
4 90 11 28
28 48 2 2
28 58 52 22
8 90 6 95
28 6 1 13
28 85 61 3
41 90 31 1
23 90 3 49
28 1 5 ...

output:

103968/1625

result:

ok single line: '103968/1625'

Test #71:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

100 100
22 85
70 85 2 4
40 85 7 76
22 1 13 23
4 85 13 46
77 85 3 22
79 85 32 2
22 76 2 24
14 85 1 9
62 85 2 3
22 86 48 34
78 85 39 5
22 100 90 6
44 85 4 1
22 6 32 5
22 67 4 6
99 85 1 1
22 55 13 37
53 85 1 2
22 56 47 4
22 84 4 6
49 85 23 53
22 18 6 81
13 99 1 33
98 85 1 1
31 85 70 12
39 85 2 1
22 15 ...

output:

2738/685

result:

ok single line: '2738/685'

Test #72:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

100 100
17 79
17 63 4 35
13 79 3 10
38 79 76 2
17 11 41 14
17 68 1 1
17 59 6 32
17 67 1 6
17 94 2 36
17 41 1 78
70 79 68 13
17 39 40 6
57 79 26 4
95 79 7 7
12 79 74 1
36 79 14 32
58 79 1 1
17 74 44 4
81 79 18 2
17 99 4 15
52 79 3 83
17 26 9 11
17 88 28 8
100 80 13 1
17 48 55 1
56 79 5 86
86 79 1 5
1...

output:

256/17

result:

ok single line: '256/17'

Test #73:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

100 100
64 13
30 37 3 4
82 13 16 32
64 33 2 43
24 13 27 4
64 20 10 67
64 48 3 2
64 68 32 90
64 65 1 1
64 30 78 3
75 13 4 8
64 38 1 1
58 13 20 5
64 16 7 61
64 15 1 30
64 53 2 11
9 13 4 1
64 50 6 6
57 13 24 45
64 61 1 12
25 13 74 6
64 89 3 2
11 13 18 44
64 54 71 26
64 6 40 3
71 13 23 28
64 12 6 29
64 ...

output:

256/65

result:

ok single line: '256/65'

Test #74:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

100 100
4 80
7 80 3 4
92 80 57 55
4 13 1 1
39 80 99 12
35 80 47 17
15 80 90 26
81 80 29 1
42 80 1 57
4 90 4 11
49 80 69 45
94 80 3 3
22 80 7 29
4 3 15 6
4 28 2 4
87 80 6 84
48 80 10 25
72 80 20 8
29 80 5 16
59 80 43 26
4 82 2 2
4 21 4 4
91 80 1 23
57 80 27 1
4 66 1 44
61 80 3 17
27 80 3 20
4 89 14 7...

output:

5625/226

result:

ok single line: '5625/226'

Test #75:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

100 100
74 80
74 50 11 16
64 80 7 4
63 80 45 93
74 67 7 4
74 56 5 14
77 80 45 9
74 25 1 2
39 80 34 28
78 80 13 4
74 68 1 1
74 97 51 13
60 80 2 30
74 45 6 7
74 71 59 3
74 16 2 31
2 80 77 36
33 80 1 4
74 99 39 1
74 51 1 20
74 46 1 4
74 94 6 1
90 80 86 2
74 23 3 7
74 24 3 22
74 47 30 33
15 80 4 1
74 83...

output:

379456/1937

result:

ok single line: '379456/1937'

Test #76:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

100 100
24 18
81 18 53 4
24 11 4 1
24 9 20 5
4 18 19 6
24 38 10 1
99 18 94 42
24 33 80 1
24 86 1 9
23 18 26 3
47 18 30 11
22 18 71 1
24 46 87 62
73 18 11 51
24 6 4 1
24 71 6 2
19 18 56 1
24 10 3 22
24 15 1 1
24 31 10 2
74 18 10 1
35 18 72 2
24 34 74 11
24 61 40 56
24 49 5 72
24 93 1 79
66 18 3 1
29 ...

output:

223729/122

result:

ok single line: '223729/122'

Test #77:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

100 100
58 81
63 81 45 5
1 81 25 16
75 81 4 4
14 81 5 4
51 81 1 13
11 81 22 44
74 81 36 72
58 84 31 1
58 100 37 1
47 81 3 32
58 8 54 1
56 81 3 3
58 97 35 22
52 81 1 30
25 81 38 24
17 81 89 15
20 81 55 16
58 55 95 15
58 92 3 16
58 72 3 21
58 80 4 82
57 81 11 75
58 77 11 52
26 81 3 73
2 81 30 13
58 39...

output:

1806336/7057

result:

ok single line: '1806336/7057'

Test #78:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

100 100
34 98
87 98 16 79
29 98 48 42
34 40 95 3
85 98 9 92
34 84 8 8
23 98 1 1
44 98 7 5
34 67 4 37
61 98 4 13
34 14 72 13
34 55 94 75
34 94 3 2
3 98 60 2
65 98 1 9
1 98 1 2
34 15 44 2
34 51 5 6
86 98 4 40
34 32 6 56
34 92 85 2
34 36 4 34
34 79 1 2
34 56 4 38
34 19 8 23
34 73 23 15
30 98 5 3
33 98 ...

output:

602802/1861

result:

ok single line: '602802/1861'

Test #79:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

100 100
93 9
7 9 1 32
93 4 83 16
76 9 44 6
21 9 41 1
55 9 2 2
93 81 20 1
58 9 14 3
60 9 3 62
93 83 3 82
93 6 15 69
93 53 57 87
77 9 18 38
93 99 52 5
87 9 19 3
93 39 13 24
88 9 4 9
81 42 1 16
93 46 65 6
63 9 61 16
93 54 78 2
93 20 16 8
52 9 3 6
93 90 77 2
93 18 39 44
93 48 9 5
22 9 1 1
31 9 1 6
84 9 ...

output:

188356/3845

result:

ok single line: '188356/3845'

Test #80:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

100 100
17 59
17 76 1 11
27 59 8 12
17 34 2 12
16 59 22 14
40 97 94 1
42 59 81 57
33 59 1 2
17 7 17 25
17 11 5 2
17 32 24 3
17 12 5 40
17 89 15 15
17 5 17 69
85 59 6 5
17 68 1 1
71 59 25 22
17 78 43 18
17 55 22 64
26 59 20 19
17 19 6 1
17 84 50 1
69 59 6 1
17 13 3 9
37 59 75 2
17 43 1 13
64 59 14 10...

output:

25600/257

result:

ok single line: '25600/257'

Test #81:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

100 911
25 6
73 10 29 11
49 81 2 66
50 68 6 1
19 73 2 25
42 86 33 3
65 47 6 1
8 2 2 2
25 32 19 1
65 41 1 7
9 68 4 66
61 24 55 58
5 59 4 13
98 33 8 8
5 8 65 16
56 59 7 2
77 94 2 15
79 45 4 3
28 76 5 60
51 41 3 12
26 17 15 17
28 41 83 1
99 78 35 7
69 53 8 1
37 70 10 1
91 34 3 3
49 70 24 59
94 31 1 1
2...

output:

0/1

result:

ok single line: '0/1'

Test #82:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

100 921
35 76
41 75 1 8
60 48 22 28
69 8 58 1
89 74 1 80
97 77 1 4
26 15 2 57
55 26 3 8
46 78 2 2
78 58 6 2
25 40 2 9
9 71 9 22
56 34 49 16
84 15 1 36
81 52 16 92
10 40 3 4
92 54 51 28
2 40 80 4
46 48 3 32
78 85 5 34
43 40 4 17
30 1 18 1
23 7 40 17
14 99 1 5
16 52 1 17
91 57 54 3
88 56 15 7
74 38 30...

output:

0/1

result:

ok single line: '0/1'

Test #83:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

100 923
31 73
13 28 70 2
65 24 14 10
95 80 2 9
16 13 16 1
50 60 13 13
75 61 3 45
5 26 88 1
5 64 1 25
63 83 3 1
86 9 1 5
42 14 25 1
78 93 1 10
23 1 88 8
44 24 7 4
34 93 5 46
41 18 51 11
67 12 26 2
100 2 27 24
86 55 85 92
74 51 1 60
13 83 29 33
76 89 50 81
57 98 35 3
37 83 13 1
46 58 2 31
74 48 15 13
...

output:

0/1

result:

ok single line: '0/1'

Test #84:

score: 0
Accepted
time: 8ms
memory: 3848kb

input:

100 196
27 26
27 72 100 100
88 26 100 100
51 26 100 100
12 26 100 100
46 26 100 100
18 26 100 100
65 26 100 100
83 26 100 100
1 26 100 100
27 82 100 100
27 21 100 100
24 26 100 100
49 26 100 100
27 30 100 100
27 57 100 100
90 26 100 100
27 25 100 100
27 56 100 100
69 26 100 100
27 11 100 100
27 23 1...

output:

3841600000000/40001

result:

ok single line: '3841600000000/40001'

Test #85:

score: 0
Accepted
time: 4ms
memory: 3684kb

input:

100 513
82 55
82 35 100 100
24 21 100 100
46 96 100 100
23 47 100 100
71 88 100 100
53 43 100 100
82 50 100 100
58 22 100 100
34 66 100 100
1 91 100 100
3 69 100 100
57 69 100 100
24 62 100 100
1 9 100 100
52 68 100 100
52 26 100 100
92 55 100 100
47 55 100 100
53 81 100 100
85 96 100 100
54 96 100 ...

output:

9734400000000/1690001

result:

ok single line: '9734400000000/1690001'

Test #86:

score: 0
Accepted
time: 13ms
memory: 3668kb

input:

100 613
48 32
36 32 100 100
80 60 100 100
53 52 100 100
65 28 100 100
6 63 100 100
43 68 100 100
37 95 100 100
37 90 100 100
29 58 100 100
51 52 100 100
20 28 100 100
63 62 100 100
85 81 100 100
85 11 100 100
62 76 100 100
21 60 100 100
70 95 100 100
16 52 100 100
26 32 100 100
53 64 100 100
58 71 1...

output:

2190400000000/40001

result:

ok single line: '2190400000000/40001'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-01-20 17:00:13 | OpenSource Project