QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235631#665. Boxes and BallsckisekiAC ✓27ms7256kbC++204.4kb2023-11-02 23:03:042023-11-02 23:03:04

Judging History

This is the latest submission verdict.

  • [2023-11-02 23:03:04]
  • Judged
  • Verdict: AC
  • Time: 27ms
  • Memory: 7256kb
  • [2023-11-02 23:03:04]
  • Submitted

answer

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

#define all(x) begin(x), end(x)
#ifdef local
#include <experimental/iterator>
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

template <typename F, typename C> class MCMF {
    static constexpr F INF_F = numeric_limits<F>::max() / 3;
    static constexpr C INF_C = numeric_limits<C>::max() / 3;
    struct E {
      int to, r;
      F f; C c;
      E() {}
      E(int a, int b, F x, C y)
        : to(a), r(b), f(x), c(y) {}
    };
    int n;
    array<vector<E>, 40000> g;
    vector<pair<int, int>> f;
    vector<bool> inq;
    vector<F> up; vector<C> d, h;
    optional<pair<F, C>> step(int S, int T) {
      safe;
      debug(S, T);
      priority_queue<pair<C, int>> q;
      q.emplace(d[S] = 0, S), up[S] = INF_F;
      while (not q.empty()) {
        auto [l, u] = q.top(); q.pop();
        debug(u, l, -d[u]);
        assert(-l >= d[u]);
        assert(up[u] != 0);
        if (l != -d[u]) continue;
        for (int i = 0; i < int(g[u].size()); ++i) {
          auto e = g[u][i]; int v = e.to;
          debug(u, v, e.c + h[u] - h[v]);
          if (e.f > 0)
            assert(e.c + h[u] - h[v] >= 0);
          auto nd = d[u] + e.c + h[u] - h[v];
          if (e.f <= 0 or d[v] <= nd) continue;
          f[v] = {u, i}; up[v] = min(up[u], e.f);
          q.emplace(-(d[v] = nd), v);
        }
      }
      if (d[T] == INF_C) return nullopt;
      for (size_t i = 0; i < d.size(); ++i)
        h[i] += d[i];
      for (int i = T; i != S; i = f[i].first) {
        auto &eg = g[f[i].first][f[i].second];
        eg.f -= up[T]; g[eg.to][eg.r].f += up[T];
      }
      return pair{up[T], h[T]};
    } 
    void precalc(int a) {
      d[a] = 0;
      for (int _ = 0; _ <= n; _++) {
        bool flag = false;
        for (int u = 0; u < n; u++)
          if (d[u] != INF_C)
            for (int i = 0; i < int(g[u].size()); ++i) {
              auto e = g[u][i]; int v = e.to;
              auto nd = d[u] + e.c;
              if (e.f <= 0 or d[v] <= nd) continue;
              d[v] = nd;
              flag = true;
            }
        if (_ == n) assert(!flag);
        if (!flag)
          break;
      }
      orange(all(d));
      assert(h.size() == d.size());
      for (size_t i = 0; i < d.size(); ++i)
        h[i] = d[i];
      debug(INF_C);
      fill(d.begin(), d.end(), INF_C);
    }
  public:
    MCMF(int n_) : n(n_), f(n), inq(n), up(n), d(n, INF_C), h(n) {}
    void add_edge(int s, int t, F c, C w) {
      g[s].emplace_back(t, int(g[t].size()), c, w);
      g[t].emplace_back(s, int(g[s].size()) - 1, 0, -w);
    }
    pair<F, C> solve(int a, int b) {
      precalc(a);
      F c = 0; C w = 0;
      while (auto r = step(a, b)) {
        c += r->first, w += r->first * r->second;
        fill(d.begin(), d.end(), INF_C);
      }
      return {c, w};
    }
};

using lld = int64_t;


using ll = lld;
const int N = 10025;

int lst[N], wei[N];
const ll MAXC = 1e9;
const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int m, n, k;
    ll ans = 0;
    cin >> m >> n >> k;
    int S = 0, T = 2 * k + 1;
    MCMF<lld,lld> mcmf(2 * k + 2);
    // mcmf.init(2 * k + 2);
    for (int i = 1; i <= n; ++i)
        cin >> wei[i];
    mcmf.add_edge(S, 1, m, 0);
    mcmf.add_edge(2 * k, T, m, 0);
    for (int i = 1; i <= k; ++i) {
        mcmf.add_edge(2 * i - 1, 2 * i, 1, -MAXC);
        mcmf.add_edge(2 * i - 1, 2 * i, INF, 0);
        if (i < k)
            mcmf.add_edge(2 * i, 2 * i + 1, INF, 0);
    }
    for (int i = 1; i <= k; ++i) {
        int x;
        cin >> x;
        if (lst[x]) mcmf.add_edge(2 * lst[x], 2 * i - 1, 1, -wei[x]);
        lst[x] = i;
        ans += wei[x];
    }
    auto [flow, cost] = mcmf.solve(S, T);
    cout << ans + k * MAXC + cost << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3 6
10
20
30
1
2
3
1
2
3

output:

60

result:

ok single line: '60'

Test #2:

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

input:

2 3 6
10
20
30
1
2
3
1
2
3

output:

80

result:

ok single line: '80'

Test #3:

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

input:

1 1 1
8916
1

output:

8916

result:

ok single line: '8916'

Test #4:

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

input:

1 1 1000
1319
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

output:

1319

result:

ok single line: '1319'

Test #5:

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

input:

1 10 1
7222
7541
665
6138
6834
8472
9450
7323
8223
1183
7

output:

9450

result:

ok single line: '9450'

Test #6:

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

input:

1 10 1000
7645
9162
2432
247
2559
3504
5683
3825
5884
5197
6
3
7
4
8
1
10
1
4
3
4
2
4
2
4
8
2
8
5
1
6
2
6
10
10
5
1
10
9
9
7
9
7
4
2
3
6
3
6
7
8
5
4
6
7
5
7
3
5
3
8
10
8
8
3
10
8
5
10
1
10
3
10
2
3
10
2
6
8
5
8
8
2
5
1
6
5
10
3
10
2
4
6
10
4
1
5
5
1
7
9
5
9
2
9
10
9
3
1
3
3
4
3
10
8
5
9
2
10
3
8
5
4...

output:

4099952

result:

ok single line: '4099952'

Test #7:

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

input:

3 1 1
2193
1

output:

2193

result:

ok single line: '2193'

Test #8:

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

input:

3 1 1000
4065
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

output:

4065

result:

ok single line: '4065'

Test #9:

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

input:

3 10 1
1235
3867
1554
3069
6439
3353
7630
6785
2834
9499
10

output:

9499

result:

ok single line: '9499'

Test #10:

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

input:

3 10 1000
5576
7215
3323
7713
5442
6754
2558
9114
4401
1911
3
6
7
4
6
1
1
3
2
2
2
4
9
3
3
6
5
10
5
2
4
9
5
5
1
5
6
7
10
5
6
7
7
7
8
2
2
1
6
10
3
2
4
2
6
1
4
3
1
6
5
9
4
1
8
10
7
4
5
4
8
1
10
8
4
8
7
1
5
5
4
3
8
1
1
1
5
3
4
8
10
7
10
2
4
3
7
3
2
7
8
1
4
4
7
9
1
9
10
3
10
8
7
6
9
3
7
1
7
10
6
5
1
2
9
...

output:

2462043

result:

ok single line: '2462043'

Test #11:

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

input:

2 5 207
3986
4810
4235
9030
5231
1
5
2
3
4
3
1
4
1
3
5
3
4
4
4
2
1
1
3
3
2
4
1
1
4
1
5
3
2
2
4
5
3
4
4
4
4
1
1
5
3
1
2
1
5
2
2
4
1
3
2
5
2
1
2
3
5
3
3
3
1
2
1
4
2
4
4
3
1
2
3
5
5
2
2
3
3
2
2
2
2
5
2
5
1
5
3
2
1
2
5
2
2
2
2
2
5
5
1
2
5
5
5
4
4
2
5
5
1
2
1
3
4
4
2
1
1
3
4
1
4
5
1
1
3
2
5
2
5
2
1
5
1
3...

output:

472094

result:

ok single line: '472094'

Test #12:

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

input:

3 10 142
9266
518
4888
4135
4691
7518
7861
6633
3574
8521
5
5
1
9
10
7
2
3
4
6
1
1
10
5
9
9
4
8
7
8
5
3
6
4
5
2
6
7
3
10
9
6
1
3
9
2
5
8
5
1
4
3
8
5
1
8
10
10
6
8
7
1
10
7
8
5
6
3
10
4
1
9
3
8
9
3
6
4
8
3
3
10
2
10
2
10
8
3
6
2
5
10
7
3
3
3
1
6
4
10
1
3
8
7
9
1
1
10
7
6
10
9
3
9
9
4
5
3
6
4
2
8
1
3
...

output:

409815

result:

ok single line: '409815'

Test #13:

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

input:

1 5 301
4045
2565
2318
2100
1010
2
4
5
5
5
5
2
1
3
5
2
2
4
3
5
2
1
3
4
2
5
3
1
1
1
1
2
1
3
2
5
2
3
2
1
1
3
3
1
1
4
5
5
3
3
4
2
1
2
5
3
1
3
1
5
5
2
1
5
1
1
3
3
4
5
5
3
5
2
5
1
4
4
3
1
2
1
5
3
1
5
3
5
1
4
4
1
5
3
5
4
3
2
5
5
3
2
3
1
4
5
2
4
3
4
2
2
3
3
1
5
2
2
4
1
2
3
2
4
4
5
5
5
2
5
5
4
3
4
1
2
3
1
5...

output:

601566

result:

ok single line: '601566'

Test #14:

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

input:

3 4 461
8190
7387
4037
5056
2
3
4
1
4
4
4
3
1
4
4
4
3
2
2
1
4
2
1
2
3
4
1
1
1
4
1
4
2
2
4
3
2
4
1
1
1
3
4
1
3
2
4
3
1
4
3
1
3
1
2
4
3
4
4
4
3
2
2
4
2
4
4
1
4
4
3
4
4
1
2
4
3
3
2
3
2
1
1
1
3
4
1
4
3
3
1
1
4
3
1
3
2
4
1
4
2
4
4
3
3
3
4
2
3
3
3
2
2
4
4
2
1
3
4
3
1
2
3
3
4
3
2
1
2
1
4
2
3
3
1
4
4
2
3
3
...

output:

406074

result:

ok single line: '406074'

Test #15:

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

input:

3 3 85
459
8759
3043
1
3
2
3
2
3
2
1
2
2
2
2
1
2
2
2
2
3
1
1
3
3
2
1
3
1
1
3
3
1
2
2
2
1
2
1
2
3
2
2
3
3
1
2
1
2
1
1
3
3
2
3
3
2
1
1
1
1
1
2
3
1
3
3
2
2
2
3
1
2
2
3
1
2
2
1
3
1
1
1
2
2
3
2
1

output:

12261

result:

ok single line: '12261'

Test #16:

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

input:

2 6 330
6412
3092
4584
8719
3590
7095
1
2
4
4
5
2
1
1
6
4
4
5
2
6
5
5
6
1
1
1
4
6
2
1
4
1
3
3
2
4
3
6
4
4
5
6
4
3
3
4
5
3
3
4
5
5
5
3
4
2
4
4
5
3
5
2
1
1
4
5
5
6
2
5
4
6
6
2
3
6
2
6
1
1
2
6
1
2
2
6
5
6
5
6
1
3
1
3
4
4
3
2
3
5
6
1
4
3
2
3
3
4
6
1
2
6
4
5
2
3
3
4
5
4
2
3
2
3
3
4
4
1
2
1
5
3
4
6
5
2
2
...

output:

894825

result:

ok single line: '894825'

Test #17:

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

input:

2 8 928
8867
1733
4402
5256
355
2130
8045
6421
7
2
2
6
6
4
3
8
5
2
1
2
5
1
4
4
8
5
6
3
7
5
2
5
3
6
6
5
5
3
4
3
4
7
6
6
3
7
2
1
6
4
1
4
2
1
6
7
2
8
6
2
2
4
6
8
5
3
1
4
3
2
1
3
2
7
3
2
4
6
7
1
6
2
7
5
5
3
4
6
1
2
5
7
5
6
7
3
8
1
8
6
1
8
5
3
2
4
6
1
3
5
1
1
4
6
1
5
8
6
6
1
8
7
8
5
6
2
1
7
1
3
3
3
4
4
1...

output:

2346574

result:

ok single line: '2346574'

Test #18:

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

input:

3 6 839
1129
3880
9479
1529
1536
4689
2
4
4
2
4
1
5
3
1
2
4
4
2
1
5
1
5
5
2
2
5
2
6
5
2
4
4
2
2
4
1
5
1
5
1
4
5
1
1
2
6
6
5
4
6
4
4
1
2
4
2
5
5
2
4
1
5
5
2
6
6
5
6
6
2
2
2
5
2
4
1
3
1
4
2
3
5
4
6
1
6
6
4
1
4
5
5
6
6
4
6
6
2
4
2
1
2
3
5
2
2
5
4
6
2
4
5
3
6
2
5
6
4
3
1
4
5
5
3
2
1
5
5
4
5
3
2
3
4
3
6
...

output:

682015

result:

ok single line: '682015'

Test #19:

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

input:

3 10 233
1280
1604
6589
590
7042
28
5408
9905
8797
4796
3
8
2
9
10
10
5
6
2
5
6
2
6
1
2
4
4
1
7
10
8
5
10
5
10
3
10
2
6
2
10
4
1
9
5
5
1
5
9
10
9
2
4
7
4
3
2
4
10
8
2
6
10
10
2
3
9
9
7
10
1
3
9
3
3
9
3
6
2
6
3
9
5
4
6
7
6
4
7
6
5
2
1
5
5
7
3
8
2
9
5
5
5
6
5
3
3
4
1
10
10
1
7
8
5
1
3
10
9
10
5
10
7
2...

output:

417958

result:

ok single line: '417958'

Test #20:

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

input:

1 8 51
4691
116
5044
5379
4979
3426
9807
8814
4
6
8
3
8
7
1
3
2
7
1
8
5
6
7
3
1
8
7
5
3
7
5
7
7
5
2
7
2
8
2
1
4
4
1
4
4
7
8
3
6
1
1
2
3
7
7
8
1
5
5

output:

264952

result:

ok single line: '264952'

Test #21:

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

input:

2 7 855
2353
7986
5342
4395
3580
5540
3132
6
5
7
3
6
3
4
7
3
2
6
4
5
6
4
3
4
6
3
3
2
2
6
6
7
6
7
3
5
6
2
2
2
4
3
6
7
4
6
4
7
5
1
5
5
4
5
7
1
3
2
2
3
4
3
1
3
1
4
3
2
7
1
6
4
5
1
5
3
4
5
7
3
4
5
3
5
7
3
5
1
7
1
5
4
4
5
3
7
1
7
5
4
3
3
5
7
4
6
2
2
4
4
6
5
7
1
5
6
4
7
6
6
3
1
3
2
3
4
2
5
7
3
1
3
2
4
1
7...

output:

2043912

result:

ok single line: '2043912'

Test #22:

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

input:

1 7 944
7561
2934
5579
8659
4252
4768
7772
7
1
1
2
7
1
5
4
7
4
6
5
2
6
3
7
5
2
5
3
1
7
6
7
5
1
4
6
1
6
3
3
2
1
5
6
1
4
6
7
4
4
6
6
4
7
5
6
5
2
7
4
1
2
6
2
4
3
4
1
3
7
4
7
6
2
7
3
4
1
1
4
1
6
2
5
1
4
3
7
1
4
6
6
6
7
3
5
5
2
7
6
7
7
5
6
4
3
4
6
2
5
2
5
7
7
5
3
2
3
5
2
1
7
3
7
1
7
6
3
2
5
3
2
1
3
2
7
2...

output:

4815562

result:

ok single line: '4815562'

Test #23:

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

input:

1 7 472
3758
5759
6576
4652
6475
2334
2293
3
7
2
5
5
6
5
4
3
7
7
1
2
5
1
4
6
3
5
6
6
7
6
3
7
6
4
7
5
5
1
2
1
2
4
1
3
6
1
3
4
3
2
2
6
6
6
7
6
3
4
6
7
2
2
3
5
2
3
7
6
5
3
2
3
7
3
6
7
4
7
3
7
6
2
1
3
4
6
5
2
7
1
4
5
1
2
5
3
3
4
6
1
3
6
5
3
4
4
1
6
7
1
7
4
4
7
6
6
2
7
7
3
5
7
2
5
4
1
1
4
7
4
6
5
4
4
2
3...

output:

1856415

result:

ok single line: '1856415'

Test #24:

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

input:

2 6 147
4951
9586
7472
3436
3523
3963
6
4
1
4
3
4
3
4
5
5
6
5
2
6
5
2
5
3
6
2
1
2
1
1
6
4
2
2
4
3
4
2
1
3
1
1
4
3
1
2
5
6
6
4
1
3
1
5
2
5
6
1
3
1
4
6
5
1
4
6
5
6
3
2
1
4
5
3
3
4
3
6
3
5
5
5
4
4
3
2
1
5
2
4
6
2
6
3
5
1
3
1
1
1
4
3
1
3
3
5
5
3
4
2
2
2
5
4
3
2
6
2
2
1
1
6
5
4
4
4
2
1
6
6
4
6
1
4
1
5
3
...

output:

376654

result:

ok single line: '376654'

Test #25:

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

input:

2 6 383
8626
3982
7035
8235
2240
1978
3
2
6
5
1
5
1
3
2
6
6
1
3
2
2
2
3
5
6
2
3
1
3
5
4
5
1
4
1
5
4
5
4
5
6
3
3
4
5
1
3
2
2
2
5
2
6
6
3
1
2
1
2
4
3
2
6
6
1
3
6
3
6
5
3
1
5
1
2
4
1
6
6
6
2
1
5
3
3
4
6
6
3
4
3
5
6
2
3
5
2
3
1
3
1
5
4
4
6
6
6
2
1
4
4
2
6
2
1
5
2
2
5
4
4
1
6
3
1
2
2
3
1
2
4
6
6
6
3
2
4
...

output:

975131

result:

ok single line: '975131'

Test #26:

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

input:

3 10 1000
8463
1878
9586
5468
698
4386
9270
585
8803
5631
9
7
7
6
4
7
8
1
1
8
1
7
2
1
2
7
6
7
3
2
8
9
3
7
9
4
5
1
1
2
8
4
3
10
3
1
7
3
5
3
4
1
6
5
6
8
3
2
1
9
2
6
10
4
9
10
3
5
1
6
1
6
6
7
2
6
2
10
6
2
9
4
9
10
5
8
6
3
3
5
3
8
2
4
5
3
8
4
3
1
2
7
8
8
8
5
4
2
4
4
6
8
1
10
7
10
5
5
6
3
10
2
5
3
7
8
2
...

output:

2260140

result:

ok single line: '2260140'

Test #27:

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

input:

3 10 1000
3686
7523
9745
8606
8188
2647
5529
6395
2289
1172
1
6
6
9
8
2
6
10
7
8
8
8
6
9
2
3
9
5
7
4
9
3
6
6
8
10
7
6
9
8
10
5
4
8
2
10
4
9
1
7
5
6
6
3
8
4
8
3
2
1
3
5
8
10
2
5
2
8
2
3
5
1
4
4
7
2
1
2
7
8
7
7
10
8
1
1
4
5
3
2
2
5
8
7
1
5
5
6
10
3
2
6
10
6
3
2
5
1
3
2
7
4
4
6
5
1
5
1
5
8
7
9
6
7
3
7
...

output:

2518552

result:

ok single line: '2518552'

Test #28:

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

input:

3 10 1000
5110
7663
9311
977
2425
7918
5098
4738
9445
168
8
9
10
7
2
3
5
3
5
8
10
1
6
1
7
5
4
4
8
4
1
1
1
1
3
2
8
3
7
3
9
7
2
10
7
5
7
7
2
6
5
4
2
5
8
4
5
2
8
4
9
6
8
5
6
2
8
3
4
8
8
1
8
6
8
1
2
1
1
2
7
5
2
2
8
5
10
5
6
6
8
5
5
1
8
9
8
10
6
8
1
3
5
8
9
6
5
4
10
10
7
7
1
9
4
3
6
8
4
1
6
8
4
4
5
9
2
1...

output:

2290844

result:

ok single line: '2290844'

Test #29:

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

input:

3 10 1000
1385
4459
4489
6403
5915
3184
1602
3325
3959
7938
8
4
6
1
9
6
5
3
4
9
2
7
2
2
4
3
4
7
6
7
6
1
9
9
9
3
5
4
10
5
5
3
4
4
10
7
5
7
8
8
9
9
8
10
7
2
1
5
8
8
3
10
7
9
1
4
1
6
4
2
6
5
7
2
6
1
6
4
9
5
8
9
2
10
5
4
4
9
4
2
1
3
10
9
2
2
6
9
4
8
6
9
8
3
2
3
3
5
9
7
9
2
7
7
7
6
3
6
2
3
6
5
1
2
8
9
10...

output:

1839751

result:

ok single line: '1839751'

Test #30:

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

input:

3 10 1000
6563
8774
1869
9819
9442
9568
7985
3914
2048
682
8
3
2
6
5
2
10
5
8
10
1
6
4
4
7
10
10
1
5
2
2
2
8
8
7
2
1
7
7
2
1
2
4
6
9
5
9
10
8
10
7
7
8
10
2
3
3
3
8
3
7
2
4
3
9
1
1
3
8
8
4
4
3
10
9
1
1
5
6
3
9
7
8
1
1
2
9
8
9
10
4
6
5
2
1
8
6
7
3
1
5
3
8
4
3
6
1
2
4
2
3
6
1
9
9
3
1
7
9
8
5
7
2
4
10
4...

output:

2657807

result:

ok single line: '2657807'

Test #31:

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

input:

3 10 1000
7524
4984
1721
7555
1973
5054
1073
1459
707
9989
7
7
3
1
4
6
3
2
1
6
7
3
9
4
6
10
7
9
4
2
4
4
5
10
3
7
5
7
1
6
4
7
4
1
5
5
1
9
6
1
9
4
5
9
3
1
9
7
3
2
9
3
7
6
8
8
2
2
6
9
10
6
3
9
4
8
1
5
10
4
8
9
8
4
4
7
5
5
9
8
6
5
6
6
3
8
4
1
5
3
6
2
4
8
10
10
3
7
4
8
1
4
3
3
10
3
4
8
5
10
10
2
3
8
9
1
...

output:

1615277

result:

ok single line: '1615277'

Test #32:

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

input:

3 10 1000
3699
7245
1226
7369
7999
3022
6830
9052
6983
1666
7
5
9
3
6
10
3
6
8
5
7
10
1
7
3
8
6
6
1
2
1
9
4
3
1
3
1
2
5
3
6
4
10
4
8
9
1
9
1
6
5
4
6
7
7
3
9
8
5
7
9
4
5
7
7
8
9
9
8
5
7
6
1
5
5
7
9
5
7
6
3
2
6
4
7
8
6
4
10
1
9
5
9
6
3
2
8
1
2
3
4
8
9
4
2
5
3
8
2
9
9
6
4
8
5
7
9
1
1
4
5
9
10
10
5
6
10...

output:

2431479

result:

ok single line: '2431479'

Test #33:

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

input:

3 10 1000
8093
5887
665
9335
6022
6794
8782
4583
2677
9405
9
6
9
1
9
9
5
7
7
9
9
2
2
9
5
9
3
9
4
6
8
7
9
2
5
4
1
2
6
5
6
5
4
2
3
7
9
6
2
2
6
7
10
10
2
9
1
10
9
8
5
2
5
6
10
1
9
5
9
3
5
10
9
6
4
1
6
2
2
7
9
10
8
1
6
6
4
6
4
8
2
10
1
4
7
8
10
7
9
7
9
9
5
1
3
3
7
8
7
5
6
2
2
7
8
7
10
10
3
7
9
10
10
2
9...

output:

2725603

result:

ok single line: '2725603'

Test #34:

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

input:

3 10 1000
1382
950
7116
3008
4636
9147
7781
9307
4202
3980
3
7
1
1
10
7
9
6
2
4
10
3
5
6
2
8
8
6
6
5
1
1
3
10
6
1
10
4
4
10
3
1
6
4
2
1
9
9
10
2
6
4
8
10
8
7
3
2
4
10
4
4
10
2
4
1
5
1
5
3
4
7
10
2
10
2
1
4
2
1
4
10
2
3
8
2
9
8
4
6
9
3
7
10
6
4
4
2
9
3
4
10
1
8
9
4
1
3
4
10
7
5
10
10
7
10
2
5
5
10
3
...

output:

2087368

result:

ok single line: '2087368'

Test #35:

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

input:

3 10 1000
5575
5894
6041
8624
4145
430
5289
3048
283
8915
8
4
1
6
10
8
6
4
9
5
9
1
10
2
4
8
5
9
10
2
4
5
2
8
7
1
8
1
4
8
10
1
8
1
8
7
2
8
6
4
7
3
9
5
5
9
10
7
2
1
7
4
7
2
8
6
6
5
9
5
10
6
5
4
4
7
2
8
4
7
7
1
1
5
2
8
4
3
2
8
10
9
3
1
2
8
1
10
3
1
2
3
8
4
9
4
7
4
5
9
5
7
7
8
8
7
4
2
8
5
3
6
8
9
3
8
4
...

output:

2093790

result:

ok single line: '2093790'

Test #36:

score: 0
Accepted
time: 22ms
memory: 7232kb

input:

10 10 10000
4954
8578
3562
8711
381
3244
4814
3367
2347
5956
5
7
8
10
9
9
7
10
7
7
8
1
5
7
5
9
2
8
9
5
4
10
10
8
1
5
10
10
8
3
3
8
5
4
2
10
3
8
3
7
7
10
3
5
7
4
5
4
2
3
2
3
4
7
2
2
10
5
8
2
9
5
4
3
4
5
10
2
8
2
2
6
7
10
8
9
2
3
10
1
7
3
8
4
4
7
2
6
10
3
3
3
3
10
10
1
6
7
7
5
7
10
7
5
5
6
9
2
10
10
4...

output:

45914

result:

ok single line: '45914'

Test #37:

score: 0
Accepted
time: 25ms
memory: 7256kb

input:

10 100 10000
7865
1307
5608
5416
4308
2170
1279
1106
3644
8967
9764
1580
8548
7472
7594
7897
7493
9116
1847
344
99
4486
9552
4942
6209
9216
6231
7034
8143
9802
3636
6671
249
467
2919
774
2881
2507
7119
8370
7575
9168
1543
3459
4632
3381
6488
78
7008
5136
5566
3785
805
3276
8715
1778
9301
1880
9713
3...

output:

30873149

result:

ok single line: '30873149'

Test #38:

score: 0
Accepted
time: 22ms
memory: 7184kb

input:

10 1000 10000
3327
5360
2960
1390
9315
8751
2691
5412
2231
7628
6526
5732
3437
7211
1640
4766
934
6486
3468
3511
2202
1489
3276
1537
657
2920
5944
8752
9141
2425
3906
4261
6971
6610
873
2135
9903
5714
7414
3838
5109
1602
4780
1346
8742
4942
9410
6792
9282
2754
9724
7686
84
9434
3990
4083
3828
1939
8...

output:

42320546

result:

ok single line: '42320546'

Test #39:

score: 0
Accepted
time: 27ms
memory: 7140kb

input:

10 10000 10000
4645
5891
1287
51
6153
2463
6953
5809
4558
1380
9741
3661
6934
3005
4680
8754
1949
8237
7131
6830
1317
700
2298
2253
1208
9419
8294
5282
8910
518
3465
5375
8165
2363
8584
5666
4553
9189
1641
8160
1756
2413
8490
78
2818
398
2743
6473
9266
6728
9181
3429
8286
5908
8991
872
2759
4633
640...

output:

47288172

result:

ok single line: '47288172'

Test #40:

score: 0
Accepted
time: 23ms
memory: 7076kb

input:

9 10 9493
6886
4700
1472
6714
7832
8893
5523
4637
3638
3667
9
6
10
2
2
4
6
6
5
4
3
5
9
5
8
3
2
8
1
5
1
9
10
3
4
10
10
9
7
6
3
1
3
2
7
5
4
6
2
8
10
2
9
3
7
9
8
2
7
9
6
5
9
9
8
9
8
1
10
1
10
8
6
3
9
7
3
5
2
5
7
6
9
4
6
3
10
2
4
8
7
1
7
8
8
5
10
5
8
7
1
2
2
6
6
8
7
6
1
10
1
1
6
2
6
10
9
4
1
9
2
1
7
8
5...

output:

1393211

result:

ok single line: '1393211'

Test #41:

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

input:

4 98 9584
3775
7230
7571
3052
4921
358
6156
3911
1541
5659
2082
6954
8281
8801
5578
7518
5163
4107
257
2649
3612
5888
8110
8625
6318
4518
5370
7407
7230
8636
2535
6700
7435
5908
2929
9937
5790
2028
2873
1340
2150
5778
2914
5412
8824
8765
8366
1447
1096
6841
937
5170
6778
6531
7953
9344
7719
2815
602...

output:

37555103

result:

ok single line: '37555103'

Test #42:

score: 0
Accepted
time: 23ms
memory: 7216kb

input:

9 931 9983
6325
9787
6903
2965
7104
3483
9161
5198
5563
8368
3281
4334
2728
9927
1405
9343
7051
7310
910
14
8258
5396
6861
4883
4678
6547
4688
4165
597
5400
4017
545
7637
9828
873
3907
3526
6129
1229
2778
888
4663
8653
747
1960
5759
77
8756
1334
3843
726
2353
9963
3101
8983
2996
2162
8878
7147
3393
...

output:

42558090

result:

ok single line: '42558090'

Test #43:

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

input:

4 9805 9566
5400
4238
2083
8833
9229
5402
6107
2064
9708
6983
3677
2157
9828
9680
4394
9882
2361
2368
1190
9439
3349
814
5530
4870
5715
9532
4909
882
1084
1054
8842
9783
8959
2533
9081
1674
4927
3223
6626
9660
7690
6929
5395
3190
7609
4089
8327
33
1659
4222
8065
9670
3459
6609
8250
2797
7083
7707
65...

output:

46475715

result:

ok single line: '46475715'

Test #44:

score: 0
Accepted
time: 22ms
memory: 7036kb

input:

9 9 9318
4153
3972
6156
3057
8674
8993
5145
7313
3538
8
2
8
9
6
5
4
6
3
8
4
4
2
5
3
4
1
7
1
5
8
1
5
9
8
7
8
9
3
9
5
9
8
5
9
7
6
5
8
2
2
5
5
4
5
3
9
7
8
4
2
3
9
2
9
2
6
3
4
4
8
2
8
6
7
7
5
2
2
5
4
2
1
3
4
9
5
2
1
9
6
4
1
4
8
9
5
5
3
4
1
4
7
2
8
3
1
1
9
5
7
4
4
6
9
7
4
6
9
6
7
4
9
8
3
3
7
1
6
9
5
3
7
...

output:

51001

result:

ok single line: '51001'

Test #45:

score: 0
Accepted
time: 10ms
memory: 7236kb

input:

3 95 9810
1516
9429
6830
802
7439
8830
2763
6893
469
2462
6343
38
6470
8837
5079
1378
5421
9976
5905
6729
5695
6349
9583
1059
2612
3278
7704
6601
9287
547
2453
6978
7112
6800
7987
8766
4782
5709
8828
7214
4078
4912
1833
1900
4081
5624
8513
6717
3971
9455
6442
1704
2763
5494
6443
5540
2437
6287
6601
...

output:

41206637

result:

ok single line: '41206637'

Test #46:

score: 0
Accepted
time: 19ms
memory: 7216kb

input:

6 971 9922
2724
4693
8477
524
2654
8722
7765
1231
9357
541
4175
9935
1572
8978
7650
8990
6034
3420
2271
7021
2532
2833
2861
939
5293
6029
2779
7802
7759
8842
3885
36
9902
4375
3568
1444
6650
1566
1727
547
7729
6393
6418
1635
863
835
4335
7159
8390
6682
9807
2215
2907
7196
5508
8994
5975
2142
2842
80...

output:

47372597

result:

ok single line: '47372597'

Test #47:

score: 0
Accepted
time: 17ms
memory: 7048kb

input:

9 9727 9594
7986
2325
2140
2727
1394
4550
4528
5445
5512
2766
3828
372
7215
883
2391
1049
174
645
422
3538
6028
5465
651
1340
7062
6814
6724
2937
2090
9637
1305
8595
9083
6955
390
7136
3197
1218
4614
4565
6753
8811
7001
3589
4284
7948
7148
8875
3887
5167
1016
2903
8856
9894
3683
5492
1023
2590
5879
...

output:

46321281

result:

ok single line: '46321281'

Test #48:

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

input:

6 95 80
9062
4199
7793
1825
4092
5101
9952
9438
3096
5115
8095
8095
3541
1728
3624
5405
1931
5767
8624
4221
771
7861
5812
4588
1471
9223
1922
3087
8568
7409
1645
7084
8804
4819
8166
5340
2698
5113
7836
3891
8000
216
9658
7714
5327
1848
2561
8976
8218
6845
291
6340
999
4739
7164
110
2315
9631
5649
26...

output:

327865

result:

ok single line: '327865'

Test #49:

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

input:

3 3 78
9031
4177
2405
2
1
1
3
3
3
3
2
2
1
1
1
3
2
1
3
1
3
2
2
2
3
3
3
2
1
3
3
1
1
3
1
1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
1
1
2
1
1
1
3
1
2
3
2
1
3
3
1
2
1
2
3
2
3
3
1
3
3
1
3
3
1
1
2

output:

15613

result:

ok single line: '15613'

Test #50:

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

input:

5 82 79
3301
3085
3629
7513
7287
2476
5067
8604
9667
1270
6292
9808
4710
4972
5442
585
7425
5071
550
6705
9739
4886
3300
1792
3595
9333
1082
3952
1796
5064
8317
3309
4819
7400
5112
5941
9716
8352
7767
4614
2513
5166
997
8316
1435
5823
1011
4515
7631
4712
3173
3871
3958
1244
2496
9677
624
2938
2469
7...

output:

294286

result:

ok single line: '294286'

Test #51:

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

input:

10 98 35
9569
9074
9554
8497
3779
1492
1663
8785
2065
4736
646
3726
8229
2718
5139
4757
5857
1732
6288
7580
4748
775
4681
7979
4882
1516
2474
1216
4334
4052
2606
4259
2913
7415
8806
32
4077
1711
3100
4363
5154
5533
8881
414
4810
8552
9752
3527
1982
6728
1374
7748
9755
6087
9713
8630
4109
7672
7910
3...

output:

186008

result:

ok single line: '186008'

Test #52:

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

input:

1 68 87
5113
8233
9162
7102
2189
471
923
1406
6338
1298
6977
2634
9658
8216
8921
4679
7578
8644
5591
3881
4405
1650
5974
6569
9106
6945
9276
2435
1609
1300
135
5302
8821
6018
5895
1277
7489
2520
4486
1694
2441
6772
109
6156
7570
8814
6229
4317
7505
2626
5371
9274
1452
4391
5250
8739
6912
4463
292
57...

output:

428456

result:

ok single line: '428456'

Test #53:

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

input:

8 10 73
7972
6837
6003
9484
4506
5451
9109
7776
6540
9206
5
7
1
9
6
10
2
3
7
4
2
1
9
3
10
6
2
2
9
9
1
5
2
8
9
7
2
7
3
1
1
2
4
2
4
6
9
4
6
3
3
9
7
1
6
3
1
1
1
4
10
10
9
1
5
2
5
2
7
5
1
2
3
1
1
2
9
1
9
8
9
2
1

output:

91102

result:

ok single line: '91102'

Test #54:

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

input:

9 57 69
591
1258
4404
3053
274
3467
6211
1160
8299
8411
2192
1342
3156
4354
5535
5290
8258
1564
5996
4268
3814
4982
3183
2226
8456
3900
9786
7761
4999
8362
2864
8014
5039
444
9810
3911
8857
4304
1182
2773
7190
4817
7305
1691
7295
7883
8093
1963
9974
7377
7662
1670
8437
7994
4079
764
6470
35
51
6
30
...

output:

217710

result:

ok single line: '217710'

Test #55:

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

input:

6 1 78
5896
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

output:

5896

result:

ok single line: '5896'

Test #56:

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

input:

8 38 27
8665
7084
3282
8870
3495
9238
754
1923
3193
8936
2402
6444
3164
5491
8276
4523
3531
1879
1801
66
3351
378
3154
3446
6546
4164
6545
3131
3030
5918
6379
2383
9876
9629
5921
9176
2829
4215
27
17
18
27
36
22
35
26
19
15
8
5
1
34
34
38
32
8
2
11
23
28
15
9
2
36
12

output:

97389

result:

ok single line: '97389'

Test #57:

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

input:

3 85 44
6968
7440
2630
6429
6171
7721
5879
5376
6873
1878
4939
7435
5531
186
6250
8185
3024
5997
7702
8554
3841
7927
639
4767
2795
4894
2870
9010
9055
6880
6873
5846
8105
7737
7319
4014
6329
6367
995
518
2217
9622
6817
187
3346
2830
7201
2128
2168
7963
6168
1323
8106
4656
3231
5688
6674
3627
6717
63...

output:

188974

result:

ok single line: '188974'

Test #58:

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

input:

1 24 7
1839
7829
6555
3069
6772
7326
1820
6707
3250
6025
2684
2885
6825
5309
5931
9517
2239
8152
9594
6111
957
4150
8425
40
6
15
5
20
14
5
20

output:

44332

result:

ok single line: '44332'

Test #59:

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

input:

9 85 99
3852
5283
6340
3257
4821
9906
5916
3937
9339
7839
7743
5875
8197
3475
3206
7575
2514
2860
5685
6325
725
3082
5444
9420
2380
2862
3178
1870
9397
4468
291
6088
8286
2226
229
5975
3335
8434
7952
4834
5813
2302
8408
5335
2876
6389
996
9973
5514
87
2606
8426
3624
1760
5498
6955
3296
8096
6765
363...

output:

331307

result:

ok single line: '331307'

Test #60:

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

input:

7 18 99
2406
1503
1379
778
5959
7188
5853
5488
3694
9238
3682
2815
9232
1216
662
1717
6505
4000
7
9
9
8
18
4
2
17
6
14
2
6
8
10
8
18
7
5
17
4
5
13
5
14
18
13
7
1
14
1
4
5
5
14
9
13
7
6
3
13
3
5
15
18
14
12
7
10
3
6
8
8
15
4
13
12
9
6
1
14
6
7
13
6
3
13
1
10
3
13
12
6
16
8
17
10
15
17
6
11
14
15
2
2
...

output:

115469

result:

ok single line: '115469'

Test #61:

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

input:

6 51 72
474
6563
6045
3317
4682
8723
496
9915
214
596
9162
274
5048
4636
677
1626
809
2701
3517
9729
4198
4608
9322
8141
2270
8710
1132
3059
55
9796
1095
4093
681
5516
4705
4034
4012
5933
8244
8392
8042
2415
9633
3462
4522
7611
9889
4555
9185
6790
3232
48
19
46
37
46
25
23
13
6
15
37
32
4
24
5
3
3
3...

output:

229110

result:

ok single line: '229110'

Test #62:

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

input:

1 43 100
9645
2313
8016
335
5111
9961
8864
1686
4629
7044
3713
7837
8753
7338
614
3848
8169
3384
4831
7767
7316
8601
9641
5675
5712
5031
6083
1875
881
2745
9038
7819
7071
4684
314
1639
8870
4552
7452
7061
1299
8125
8223
18
10
22
36
32
38
40
4
33
1
42
31
19
18
18
39
31
9
34
2
7
20
41
38
39
38
36
30
2...

output:

561803

result:

ok single line: '561803'

Test #63:

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

input:

10 66 82
9945
7762
4805
2786
3380
2838
9403
4659
9140
6392
9362
3758
8255
2510
5292
9897
9526
7448
6227
4251
4175
6929
1254
4612
8445
7289
4616
4941
5214
3290
6794
4529
210
630
5653
3298
3483
6915
8400
6471
6753
3954
9431
8873
5732
9
6262
3544
3223
6371
5304
6191
4683
9044
4145
9396
9431
3131
9030
6...

output:

311378

result:

ok single line: '311378'

Test #64:

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

input:

10 22 99
532
7334
7332
7301
1945
4777
8349
2662
1911
1984
5788
2224
9985
7481
2274
4865
5886
7699
3654
7706
429
7672
1
18
20
6
21
17
12
17
4
18
20
19
6
20
9
12
15
21
10
21
11
9
5
7
11
3
21
15
3
12
12
19
4
9
8
12
13
17
11
19
17
10
19
11
8
2
1
19
16
14
10
9
9
19
6
6
17
5
19
16
19
1
11
9
22
10
16
9
5
4...

output:

152315

result:

ok single line: '152315'

Test #65:

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

input:

6 4 71
8856
6630
4905
188
2
4
1
1
2
4
3
4
2
2
3
2
2
4
4
3
2
3
4
4
2
4
2
4
2
4
2
3
4
4
4
3
3
2
4
1
1
2
3
2
4
2
4
4
3
2
1
2
4
1
3
4
2
2
1
4
1
2
4
3
1
2
3
4
1
1
4
2
4
4
1

output:

20579

result:

ok single line: '20579'

Test #66:

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

input:

4 53 15
7744
3202
9498
6019
8976
376
5435
3147
3018
6611
4503
4148
7280
8419
8311
7042
3785
7055
8142
7282
5329
6592
7177
2837
6175
9116
8892
4477
3863
1226
3226
1232
9955
6900
3957
7589
6849
5662
8044
8616
837
1824
7878
5919
8975
763
8548
4149
3374
6648
1909
7427
8674
53
45
47
6
13
6
19
31
18
25
11...

output:

90422

result:

ok single line: '90422'

Test #67:

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

input:

5 83 40
8269
154
6911
6408
4574
7657
392
9693
6211
5061
2368
4922
8566
8660
6176
4221
7519
5674
9220
2539
2936
301
8381
2182
639
7601
6907
1583
2997
2848
2286
8582
2145
8714
1813
6026
2900
1479
7969
7696
2225
264
4843
2522
2744
4938
672
6917
7869
2294
2834
4475
6541
2328
4527
5870
6143
559
6815
1066...

output:

144985

result:

ok single line: '144985'