QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#810720#130. Cost Performance Flowcdx123456WA 22ms3932kbC++142.1kb2024-12-12 09:46:002024-12-12 09:46:01

Judging History

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

  • [2024-12-12 09:46:01]
  • 评测
  • 测评结果：WA
  • 用时：22ms
  • 内存：3932kb
查看
  • [2024-12-12 09:46:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int __int128
int cnt=-1,ans,anss,t,d[110],f[110],head[110],pre[110],inf=1e9;
long long n,m,s,T;
bool qi[110];
struct ee{
	int next,to,dis,w;
}e[3010];
struct fs{
	int fz,fm;
};
int gcd(int x,int y){
	if(!y) return x;
	return gcd(y,x%y);
}
bool operator < (fs x,fs y){
	return x.fz*y.fm<y.fz*x.fm;
}
void add(int x,int y,int ff,int w){
	e[++cnt].to=y;
	e[cnt].next=head[x];
	e[cnt].dis=ff;
	e[cnt].w=w;
	head[x]=cnt;
}
bool spfa(){
	queue<int> q; 
	memset(d,0x3f,sizeof(d));
	memset(f,0,sizeof(f));
	f[s]=inf;
	d[s]=0;
	qi[s]=1;
	q.push(s);
	while(!q.empty()){
		int x=q.front(); q.pop(); qi[x]=0;
		for(int i=head[x];i!=-1;i=e[i].next){
			if(e[i].dis && d[e[i].to]>d[x]+e[i].w){
				d[e[i].to]=d[x]+e[i].w;    f[e[i].to]=min(f[x],e[i].dis);    pre[e[i].to]=i;
				if(qi[e[i].to]) continue;
				qi[e[i].to]=1;; q.push(e[i].to);
			}
		}
	}
	return f[t]>0;
}
void ek(){
	while(spfa()){
		ans+=f[t]*d[t];
		anss+=f[t];
		for(int i=t;i!=s;i=e[pre[i]^1].to){
			e[pre[i]].dis-=f[t]; e[pre[i]^1].dis+=f[t]; 
		}
	}
}
signed main(){
	long long x,y,z,w;
	memset(head,-1,sizeof(head));
	cin>>n>>m>>s>>T;
	t=n+1;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z>>w;
		add(x,y,z,w);
		add(y,x,0,-w);
	}
	add(T,t,inf,0);
	add(t,T,0,0);
	ek();
	for(int i=0;i<=cnt;i+=2) e[i].dis+=e[i^1].dis,e[i^1].dis=0;
	e[cnt-1].dis-=inf;
	ans=0;
	
	int M=anss,lans=0;
	fs minn;
	for(int i=0;i<M;i++){
		e[cnt-1].dis++;
		ek();
		w=ans-lans;
		fs k;
		if(2*(M-i)-lans*w*2<=0){
			k.fz=lans*lans+(M-i)*(M-i);
			k.fm=1;
		}else if(2*(M-i)-lans*w*2>=2*w*w+2){
			k.fz=lans*lans+w*w+(lans*w*2-2*(M-i))+(M-i)*(M-i)+1;
			k.fm=1;
		}else{
			k.fz=2*(M-i)-lans*w*2;
			k.fm=2*w*w+2;
			k.fz=(k.fz*k.fz*(w*w+1)+k.fz*k.fm*(lans*w*2-2*(M-i))+k.fm*k.fm*(lans*lans+(M-i)*(M-i)));
			k.fm*=k.fm;
		}
		x=gcd(k.fz,k.fm);
		k.fz/=x;
		k.fm/=x;
		if(i==0 || k<minn) minn=k;
		lans=ans;
	}
	cout<<(long long)minn.fz<<'/'<<(long long)minn.fm<<endl;
	return 0;
}
//lans^2+x*x*(w^2+1)+x*(lans*w-2*(M-i))+(M-i)^2
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

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: 3664kb

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: 3548kb

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: 3580kb

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: 1ms
memory: 3608kb

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: 3552kb

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: 3608kb

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: 3608kb

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: 3604kb

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: 1ms
memory: 3648kb

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: 1ms
memory: 3588kb

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: 3612kb

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: 3808kb

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: 0ms
memory: 3812kb

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: 0ms
memory: 3536kb

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: 0ms
memory: 3592kb

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: 0ms
memory: 3604kb

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: 0ms
memory: 3784kb

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: 3584kb

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: 3608kb

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: 3608kb

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: 3488kb

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: 3616kb

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: 3784kb

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: 3492kb

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: 3540kb

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: 1ms
memory: 3608kb

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: 1ms
memory: 3616kb

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: 1ms
memory: 3816kb

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: 0ms
memory: 3816kb

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: 1ms
memory: 3544kb

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: 3492kb

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: 0ms
memory: 3792kb

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: 3816kb

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: 3824kb

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: 3612kb

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: 0ms
memory: 3588kb

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: 3744kb

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: 3816kb

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: 3544kb

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: 10ms
memory: 3652kb

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: 10ms
memory: 3704kb

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: 8ms
memory: 3928kb

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: 13ms
memory: 3720kb

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: 9ms
memory: 3928kb

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: 11ms
memory: 3724kb

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: 13ms
memory: 3900kb

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: 13ms
memory: 3852kb

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: 10ms
memory: 3728kb

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: 2ms
memory: 3660kb

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: 8ms
memory: 3716kb

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: 9ms
memory: 3732kb

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: 9ms
memory: 3856kb

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: 10ms
memory: 3728kb

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: 22ms
memory: 3652kb

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: 14ms
memory: 3932kb

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: 3ms
memory: 3724kb

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: 10ms
memory: 3720kb

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: 7ms
memory: 3700kb

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: 17ms
memory: 3656kb

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: 3604kb

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: 0ms
memory: 3540kb

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: 3788kb

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: 0ms
memory: 3744kb

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: 3588kb

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: 0ms
memory: 3812kb

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: 3552kb

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: 0ms
memory: 3540kb

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: 3612kb

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: 0ms
memory: 3808kb

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: 3436kb

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: 3588kb

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: 3612kb

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: 3604kb

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: 3604kb

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: 3648kb

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: 3748kb

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: 3612kb

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: 3612kb

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: 3540kb

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: -100
Wrong Answer
time: 1ms
memory: 3656kb

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/0

result:

wrong answer 1st lines differ - expected: '0/1', found: '0/0'
English 繁體中文 简体中文

伺服器時間: 2025-02-01 16:48:58 | 開源專案