QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408883#130. Cost Performance Flowi_am_noob#WA 6ms3952kbC++143.9kb2024-05-11 10:38:512024-05-11 10:38:52

Judging History

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

  • [2024-05-11 10:38:52]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3952kb
  • [2024-05-11 10:38:51]
  • 提交

answer

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

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())

const int N=1005,M=2005;
template<typename T1, typename T2>
struct MCMF{
    const T1 INF1=1<<30;
    const T2 INF2=1<<30;
    struct edge{
        int v; T1 f; T2 c;
    }E[M<<1];
    vector<int> adj[N];
    T2 dis[N],pot[N];
    int rt[N],vis[N],n,m,s,t;
    bool SPFA(){
        fill_n(rt,n,-1),fill_n(dis,n,INF2);
        fill_n(vis,n,false);
        queue<int> q;
        q.push(s),dis[s]=0,vis[s]=true;
        while(!q.empty()){
            int v=q.front(); q.pop();
            vis[v]=false;
            for(int id: adj[v]){
                auto [u,f,c]=E[id];
                T2 ndis=dis[v]+c+pot[v]-pot[u];
                if(f>0&&dis[u]>ndis){
                    dis[u]=ndis,rt[u]=id;
                    if(!vis[u]) vis[u]=true,q.push(u);
                }
            }
        }
        return dis[t]!=INF2;
    }
    bool dijkstra(){
        fill_n(rt,n,-1),fill_n(dis,n,INF2);
        priority_queue<pair<T2,int>,vector<pair<T2,int>>,greater<pair<T2,int>>> pq;
        dis[s]=0,pq.emplace(dis[s],s);
        while(!pq.empty()){
            auto [d,v]=pq.top(); pq.pop();
            if(dis[v]<d) continue;
            for(int id: adj[v]){
                auto [u,f,c]=E[id];
                T2 ndis=dis[v]+c+pot[v]-pot[u];
                if(f>0&&dis[u]>ndis){
                    dis[u]=ndis,rt[u]=id;
                    pq.emplace(ndis,u);
                }
            }
        }
        return dis[t]!=INF2;
    }
    vector<pair<T1,T2>> solve(int _s, int _t){
        s=_s,t=_t,fill_n(pot,n,0);
        T1 flow=0; T2 cost=0; bool fr=true;
        vector<pair<T1,T2>> res;
        res.pb({0,0});
        while(fr?SPFA():dijkstra()){
            for(int i=0; i<n; ++i) dis[i]+=pot[i]-pot[s];
            T1 add=INF1;
            for(int i=t; i!=s; i=E[rt[i]^1].v) add=min(add,E[rt[i]].f);
            for(int i=t; i!=s; i=E[rt[i]^1].v) E[rt[i]].f-=add,E[rt[i]^1].f+=add;
            flow+=add,cost+=add*dis[t],fr=false;
            res.pb({flow,cost});
            for(int i=0; i<n; ++i) swap(dis[i],pot[i]);
        }
        return res;
    }
    void init(int _n){
        n=_n,m=0;
        for(int i=0; i<n; ++i) adj[i].clear();
    }
    void add_edge(int u, int v, T1 f, T2 c){
        adj[u].pb(m),E[m++]={v,f,c};
        adj[v].pb(m),E[m++]={u,0,-c};
    }
};
MCMF<ll,ll> g;

int n,m,s,t;

pll operator + (pll a, pll b){return {a.first*b.second+b.first*a.second,a.second*b.second};}
pll operator - (pll a, pll b){return {a.first*b.second-b.first*a.second,a.second*b.second};}
pll operator * (pll a, pll b){return {a.first*b.first,a.second*b.second};}
bool cmp(pll a, pll b){return a.first*b.second<b.first*a.second;}
void chmin(pll &a, pll b){if(cmp(b,a)) a=b;}

signed main(){
    cin >> n >> m >> s >> t; s--,t--;
    g.init(n);
    for(int i=0; i<m; ++i){
        int a,b,u,c; cin >> a >> b >> u >> c; a--,b--;
        g.add_edge(a,b,u,c);
    }
    vector<pll> vec=g.solve(s,t);
    ll mx=vec.back().first;
    #define sq(x) ((x)*(x))
    pll res={sq(mx),1};
    for(int i=0; i<sz(vec); ++i) chmin(res,pll(sq(vec[i].second)+sq(mx-vec[i].first),1));
    //for(auto &[i,j]: vec) cout << i << ' ' << j << endl;
    for(int i=0; i+1<sz(vec); ++i){
        ll a1=vec[i].first,a2=vec[i].second;
        ll b=(vec[i+1].second-vec[i].second)/(vec[i+1].first-vec[i].first);
        pll cur={mx-a1-a2*b,b*b+1};
        if(cur.first>0&&cur.first<cur.second*(vec[i+1].first-vec[i].first)){
            pll de1=pll(a2,1)+cur*pll(b,1),de2=pll(mx-a1,1)-cur;
            chmin(res,sq(de1)+sq(de2));
        }
    }
    ll g=__gcd(res.first,res.second);
    res.first/=g,res.second/=g;
    cout << res.first << '/' << res.second << "\n";
}

詳細信息

Test #1:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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:

971616496042119168/2560256009600160001

result:

wrong answer 1st lines differ - expected: '3841600000000/40001', found: '971616496042119168/2560256009600160001'