QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398724#130. Cost Performance Flowhos_lyricAC ✓3ms4172kbC++148.2kb2024-04-25 17:19:392024-04-25 17:19:40

Judging History

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

  • [2024-04-25 17:19:40]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:4172kb
  • [2024-04-25 17:19:39]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_

#include <stdio.h>
#include <iostream>

constexpr unsigned __int128 toUInt128(const char *s) {
  unsigned __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
constexpr __int128 toInt128(const char *s) {
  if (*s == '-') return -toInt128(s + 1);
  __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
unsigned __int128 inUInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toUInt128(buf);
}
__int128 inInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toInt128(buf);
}

void out(unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
  if (x < 0) {
    putchar('-');
    out(-static_cast<unsigned __int128>(x));
  } else {
    out(static_cast<unsigned __int128>(x));
  }
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) os << buf[i];
  return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
  if (x < 0) {
    os << '-' << -static_cast<unsigned __int128>(x);
  } else {
    os << static_cast<unsigned __int128>(x);
  }
  return os;
}

#endif  // LIBRA_OTHER_INT128_H_

using INT = __int128;


// Minimum cost flow by successive shortest paths.
// Assumes that there exists no negative-cost cycle.
// TODO: Check the range of intermediate values.
template <class Flow, class Cost> struct MinCostFlow {
  // Watch out when using types other than int and long long.
  static constexpr Flow FLOW_EPS = 1e-10L;
  static constexpr Flow FLOW_INF = std::numeric_limits<Flow>::max();
  static constexpr Cost COST_EPS = 1e-10L;
  static constexpr Cost COST_INF = std::numeric_limits<Cost>::max();

  int n, m;
  vector<int> ptr, nxt, zu;
  vector<Flow> capa;
  vector<Cost> cost;

  explicit MinCostFlow(int n_) : n(n_), m(0), ptr(n_, -1) {}
  void ae(int u, int v, Flow w, Cost c) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(0 <= w);
    nxt.push_back(ptr[u]); zu.push_back(v); capa.push_back(w); cost.push_back( c); ptr[u] = m++;
    nxt.push_back(ptr[v]); zu.push_back(u); capa.push_back(0); cost.push_back(-c); ptr[v] = m++;
  }

  vector<Cost> pot, dist;
  vector<bool> vis;
  vector<int> pari;

  // cost slopes[j] per flow when flows[j] <= flow <= flows[j + 1]
  vector<Flow> flows;
  vector<Cost> slopes;

  // Finds a shortest path from s to t in the residual graph.
  // O((n + m) log m) time.
  //   Assumes that the members above are set.
  //   The distance to a vertex might not be determined if it is >= dist[t].
  //   You can pass t = -1 to find a shortest path to each vertex.
  void shortest(int s, int t) {
    using Entry = pair<Cost, int>;
    priority_queue<Entry, vector<Entry>, std::greater<Entry>> que;
    for (int u = 0; u < n; ++u) { dist[u] = COST_INF; vis[u] = false; }
    for (que.emplace(dist[s] = 0, s); !que.empty(); ) {
      const Cost c = que.top().first;
      const int u = que.top().second;
      que.pop();
      if (vis[u]) continue;
      vis[u] = true;
      if (u == t) return;
      for (int i = ptr[u]; ~i; i = nxt[i]) if (capa[i] > FLOW_EPS) {
        const int v = zu[i];
        if (!vis[v]) {
          const Cost cc = c + cost[i] + pot[u] - pot[v];
          if (dist[v] > cc) { que.emplace(dist[v] = cc, v); pari[v] = i; }
        }
      }
    }
  }

  // Finds a minimum cost flow from s to t of amount min{(max flow), limFlow}.
  //   Bellman-Ford takes O(n m) time, or O(m) time if there is no negative-cost
  //   edge, or cannot stop if there exists a negative-cost cycle.
  //   min{(max flow), limFlow} shortest paths if Flow is an integral type.
  pair<Flow, Cost> run(int s, int t, Flow limFlow = FLOW_INF) {
    assert(0 <= s); assert(s < n);
    assert(0 <= t); assert(t < n);
    assert(s != t);
    assert(0 <= limFlow);
    pot.assign(n, 0);
    for (; ; ) {
      bool upd = false;
      for (int i = 0; i < m; ++i) if (capa[i] > FLOW_EPS) {
        const int u = zu[i ^ 1], v = zu[i];
        const Cost cc = pot[u] + cost[i];
        if (pot[v] > cc + COST_EPS) { pot[v] = cc; upd = true; }
      }
      if (!upd) break;
    }
    dist.resize(n);
    vis.resize(n);
    pari.resize(n);
    Flow totalFlow = 0;
    Cost totalCost = 0;
    flows.clear(); flows.push_back(0);
    slopes.clear();
    for (; totalFlow < limFlow; ) {
      shortest(s, t);
      if (!vis[t]) break;
      for (int u = 0; u < n; ++u) pot[u] += min(dist[u], dist[t]);
      Flow f = limFlow - totalFlow;
      for (int v = t; v != s; ) {
        const int i = pari[v]; if (f > capa[i]) { f = capa[i]; } v = zu[i ^ 1];
      }
      for (int v = t; v != s; ) {
        const int i = pari[v]; capa[i] -= f; capa[i ^ 1] += f; v = zu[i ^ 1];
      }
      totalFlow += f;
      totalCost += f * (pot[t] - pot[s]);
      flows.push_back(totalFlow);
      slopes.push_back(pot[t] - pot[s]);
    }
    return make_pair(totalFlow, totalCost);
  }
};

////////////////////////////////////////////////////////////////////////////////


INT sq(INT r) { return r * r; }

int N, M;
int S, T;
vector<int> A, B, W, C;

int main() {
  for (; ~scanf("%d%d", &N, &M); ) {
    scanf("%d%d", &S, &T);
    --S;
    --T;
    A.resize(M);
    B.resize(M);
    W.resize(M);
    C.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%d%d", &A[i], &B[i], &W[i], &C[i]);
      --A[i];
      --B[i];
    }
    
    MinCostFlow<INT, INT> mcf(N);
    for (int i = 0; i < M; ++i) {
      mcf.ae(A[i], B[i], W[i], C[i]);
    }
    mcf.run(S, T);
    const int len = mcf.slopes.size();
    const auto &X = mcf.flows;
    vector<INT> Y(len + 1, 0);
    for (int i = 0; i < len; ++i) Y[i + 1] = Y[i] + (X[i + 1] - X[i]) * mcf.slopes[i];
    const INT F = X[len];
// cerr<<"X = "<<X<<endl;
// cerr<<"Y = "<<Y<<endl;
    
    // dist^2 between (F, 0) and polyline
    INT pm = 1, qm = 0;
    auto check = [&](INT p, INT q) -> void {
      if (pm * q > p * qm) {
        pm = p;
        qm = q;
      }
    };
    
    for (int i = 0; i <= len; ++i) {
      check(sq(X[i] - F) + sq(Y[i] - 0), 1);
    }
    for (int i = 0; i < len; ++i) {
      if ((X[i + 1] - X[i]) * (F - X[i    ]) + (Y[i + 1] - Y[i]) * (0 - Y[i    ]) > 0 &&
          (X[i] - X[i + 1]) * (F - X[i + 1]) + (Y[i] - Y[i + 1]) * (0 - Y[i + 1]) > 0) {
        const INT p = sq((F - X[i + 1]) * (0 - Y[i]) - (F - X[i]) * (0 - Y[i + 1]));
        const INT q = sq(X[i + 1] - X[i]) + sq(Y[i + 1] - Y[i]);
        check(p, q);
      }
    }
    
    const INT g = __gcd(pm, qm);
    pm /= g;
    qm /= g;
    
    out(pm);
    printf("/");
    out(qm);
    puts("");
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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