3 5
2 1 608591421 720962564
3 2 608591421 641991574
3 2 718110706 353409763
2 3 482786015 858341723
3 2 825397574 357507279
 2 1
2 1 317425595 636156322
 50000 1
20845 28516 904146168 997637433

Yes
641991574 1
2 
 Yes
0 0

 Yes
0 0


#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
pair<pair<int, int>, long long> a[4000005];
int arr[30005], n = 4000000;
long long sm[30005];
int main() {
  srand(19360817);
  int i, j, k, cnt = 0, fff = 0;
  long long sum = 0LL;
  for (i = 0; i < n; ++i) {
    long long v = (long long)rand() * (long long)rand();
    a[i] = make_pair(make_pair(rand(), rand()), v);
  }
  sort(a, a + i);
  for (i = 0; i < 30000; ++i) arr[i] = rand() + 900000000;
  for (i = 29999; i >= 1; --i) {
    for (j = 1; j <= i; ++j) {
      if (arr[j] < arr[j - 1]) {
        swap(arr[j], arr[j - 1]);
        ++fff;
        if (cnt < n) {
          sum += sm[29999 - (cnt & 1)] - sm[cnt & 1];
          if (fff >= a[cnt].first.first) {
            fff += 3;
            sum += sm[29899 - (cnt & 1)] - sm[cnt & 1];
          }
          ++cnt;
        }
      }
    }
    sm[0] = 0;
    for (j = 1; j < 30000; ++j) {
      sm[j] = sm[j - 1] + arr[j];
    }
  }
  printf("%d %I64d %d\n", cnt, sum, arr[0]);
  return 0;
}
