#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

static constexpr int MAXN = 47;
static constexpr int SLOT_MIN = 5;
static constexpr int DAY_START_MIN = 6 * 60;   // 06:00
static constexpr int DAY_END_MIN   = 21 * 60;  // 21:00
static constexpr int TS = (DAY_END_MIN - DAY_START_MIN) / SLOT_MIN + 1; // 181
static constexpr int V  = MAXN * TS;

// ===== Fixed hyperparameters =====
static constexpr int ORIGIN_USE = 47;
static constexpr int START_USE  = 47;
static constexpr int NEAR_CAND  = 18;
static constexpr int POP_CAND   = 26;

static constexpr int K_FIXED = 25;
static constexpr int M_FIXED = 400;
static constexpr int BEAM_WIDTH_DEFAULT = 3;
static constexpr int BRANCHES_DEFAULT = 2;
static int gBeamWidth = BEAM_WIDTH_DEFAULT;
static int gBranches = BRANCHES_DEFAULT;

// Tunable parameters for tie-breaking / branch scoring.
static int gTieMove = 0;
static int gTiePopDiv = 0;
static int gTieArr = 1;
static int gBranchMode = 0; // 0: default, 1: spatial-diverse, 2: time-diverse
static int gBranchDivW = 0;
static int gScoreMode = 1; // 0: cumulative dp, 1: parent true + dp
static long long gBeamGap = 100; // keep states with score >= best - gap
static int gVerboseStep = 0;
static long long gEvalFlightW = 0;
static long long gEvalPopDivW = 1;
static long long gEvalLateArrW = 0;

// Targets: 11:00, 11:30, ..., 21:00 (21 values)
static constexpr int TGT = 21;

struct FlightOut {
  int a, b;
  int dep_t, arr_t; // time index
};

struct RouteCandidate {
  vector<FlightOut> flights;
  __int128 value;
};

static inline int timeToIdx(int minute) { return (minute - DAY_START_MIN) / SLOT_MIN; }
static inline int idxToTime(int idx) { return DAY_START_MIN + idx * SLOT_MIN; }
static inline string fmtTimeIdx(int idx) {
  int m = idxToTime(idx);
  int hh = m / 60, mm = m % 60;
  char buf[6];
  snprintf(buf, sizeof(buf), "%02d:%02d", hh, mm);
  return string(buf);
}
static inline int parseTimeStr(const string& s) {
  int hh = (s[0]-'0')*10 + (s[1]-'0');
  int mm = (s[3]-'0')*10 + (s[4]-'0');
  return hh*60 + mm;
}

static inline bool parseEnvInt(const char* name, int& out) {
  const char* s = getenv(name);
  if (!s) return false;
  out = atoi(s);
  return true;
}

// ===== globals =====
static uint32_t popW[MAXN];
static int N, R;

static int durSlot[MAXN][MAXN];
static double distMat[MAXN][MAXN];
static bool validPair[MAXN][MAXN];

// earliest[d][t][c] (time-major for cache)
static uint16_t earliestSq[MAXN][TS][MAXN];
static uint16_t earliestCi[MAXN][TS][MAXN];
static constexpr uint16_t INF16 = 65535;

// latest[o][d][deadline] (same as before)
static int16_t latestSq[MAXN][MAXN][TS];
static int16_t latestCi[MAXN][MAXN][TS];

static int16_t s_sq[MAXN][MAXN][TGT];
static int16_t s_ci[MAXN][MAXN][TGT];

// reachMask[vtx][ti] : destinations reachable by target ti from vtx
static uint64_t reachMask[V][TGT];

// flipMask[oi][s][ti]  (IMPORTANT: ti contiguous now)
static uint64_t flipMask[ORIGIN_USE][TS][TGT];

static int tgtIdx[TGT];
static int firstTiTime[TS]; // first target index whose deadline >= timeIdx (or TGT)

// Precomputed feasible flight transitions from each vertex (c,t).
static uint8_t dpMoveCnt[V];
static uint16_t dpMoveV[V][MAXN];
static uint8_t dpMoveStartTi[V][MAXN];

static inline long long routeEvalBonus(const vector<FlightOut>& flights) {
  long long bonus = 0;
  bonus += gEvalFlightW * (long long)flights.size();
  if (!flights.empty()) {
    long long popDiv = 0;
    int lastArr = flights.back().arr_t;
    bool seen[MAXN];
    memset(seen, 0, sizeof(seen));
    for (const auto& f : flights) {
      if (!seen[f.b]) {
        seen[f.b] = true;
        popDiv += popW[f.b] / 1000;
      }
    }
    bonus += gEvalPopDivW * popDiv;
    bonus += gEvalLateArrW * (long long)lastArr;
  }
  return bonus;
}

// ===== sumW(mask) tables =====
static uint32_t T0[1<<16];
static uint32_t T1[1<<16];
static uint32_t T2[1<<15];

static inline void buildWeightTables(const uint32_t* w) {
  T0[0]=0;
  for (uint32_t m=1; m<(1u<<16); m++) {
    uint32_t b = __builtin_ctz(m);
    T0[m] = T0[m & (m-1)] + w[b];
  }
  T1[0]=0;
  for (uint32_t m=1; m<(1u<<16); m++) {
    uint32_t b = __builtin_ctz(m);
    T1[m] = T1[m & (m-1)] + w[16 + b];
  }
  T2[0]=0;
  for (uint32_t m=1; m<(1u<<15); m++) {
    uint32_t b = __builtin_ctz(m);
    T2[m] = T2[m & (m-1)] + w[32 + b];
  }
}
static inline uint64_t sumW_mask(uint64_t mask) {
  uint32_t a = (uint32_t)(mask & 0xFFFFull);
  uint32_t b = (uint32_t)((mask >> 16) & 0xFFFFull);
  uint32_t c = (uint32_t)((mask >> 32) & 0x7FFFull);
  return T0[a] + T1[b] + T2[c];
}

// ===== CSR adjacency (contiguous edges per u) =====
template<int MAXE>
struct CSRAdj {
  int E = 0;
  int u[MAXE];
  uint8_t toCity[MAXE];
  uint8_t arrT[MAXE];

  int start[V+1];        // size V+1
  uint8_t bTo[MAXE];
  uint8_t bArr[MAXE];

  void init() { E = 0; }

  inline void addEdge(int uV, int vCity, int at) {
    u[E] = uV;
    toCity[E] = (uint8_t)vCity;
    arrT[E] = (uint8_t)at;
    ++E;
  }

  void build() {
    static int cnt[V];
    static int cur[V];
    memset(cnt, 0, sizeof(cnt));
    for (int i=0;i<E;i++) cnt[u[i]]++;

    start[0] = 0;
    for (int i=0;i<V;i++) start[i+1] = start[i] + cnt[i];

    memcpy(cur, start, sizeof(int)*V);
    for (int i=0;i<E;i++) {
      int pos = cur[u[i]]++;
      bTo[pos]  = toCity[i];
      bArr[pos] = arrT[i];
    }
  }
};

static CSRAdj<M_FIXED + 8> sqAdj;
static CSRAdj<20000> ciAdj;

// ===== build earliest + latest =====
template<int MAXE>
static inline void buildEarliestTable(const CSRAdj<MAXE>& adj,
                                      uint16_t earliest[MAXN][TS][MAXN]) {
  // earliest[d][t][c] = min arrival time at d starting from (c,t)
  for (int d=0; d<N; d++) {
    for (int t=TS-1; t>=0; --t) {
      uint16_t* row = earliest[d][t];
      uint16_t* rowWait = (t+1 < TS) ? earliest[d][t+1] : nullptr;

      for (int c=0; c<N; c++) {
        uint16_t best = INF16;
        if (c == d) best = (uint16_t)t;
        if (rowWait) best = min(best, rowWait[c]); // wait

        int uV = c*TS + t;
        for (int ei = adj.start[uV]; ei < adj.start[uV+1]; ++ei) {
          best = min(best, earliest[d][adj.bArr[ei]][adj.bTo[ei]]);
        }
        row[c] = best;
      }
    }
  }
}

static inline void buildLatestTable(const uint16_t earliest[MAXN][TS][MAXN],
                                    int16_t latest[MAXN][MAXN][TS]) {
  // latest[o][d][deadline] from earliest
  static int16_t bucket[TS];
  for (int o=0; o<N; o++) {
    for (int d=0; d<N; d++) {
      for (int i=0;i<TS;i++) bucket[i] = -1;
      for (int s=0; s<TS; s++) {
        uint16_t arr = earliest[d][s][o];
        if (arr != INF16) bucket[arr] = max(bucket[arr], (int16_t)s);
      }
      int16_t best = -1;
      for (int dead=0; dead<TS; dead++) {
        best = max(best, bucket[dead]);
        latest[o][d][dead] = best;
      }
    }
  }
}

template<int MAXE>
static inline void buildEarliestAndLatest(const CSRAdj<MAXE>& adj,
                                          uint16_t earliest[MAXN][TS][MAXN],
                                          int16_t latest[MAXN][MAXN][TS]) {
  buildEarliestTable(adj, earliest);
  buildLatestTable(earliest, latest);
}

static void buildTargetsFromLatest(const int16_t latest[MAXN][MAXN][TS],
                                  int16_t out[MAXN][MAXN][TGT]) {
  for (int o=0; o<N; o++)
    for (int d=0; d<N; d++)
      for (int ti=0; ti<TGT; ti++)
        out[o][d][ti] = latest[o][d][tgtIdx[ti]];
}

// ===== reachMask: O(V*(N+TGT)) =====
static void buildReachMaskFromEarliestFast(const uint16_t earliest[MAXN][TS][MAXN]) {
  uint64_t tmp[TGT];
  for (int vtx=0; vtx<N*TS; vtx++) {
    int c = vtx / TS;
    int t = vtx % TS;
    for (int i=0;i<TGT;i++) tmp[i]=0;

    for (int d=0; d<N; d++) {
      uint16_t arr = earliest[d][t][c];
      if (arr == INF16) continue;
      int k = firstTiTime[(int)arr];
      if (k < TGT) tmp[k] |= (1ull << d);
    }

    uint64_t cur=0;
    for (int ti=0; ti<TGT; ti++) {
      cur |= tmp[ti];
      reachMask[vtx][ti] = cur;
    }
  }
}

// build flipMask[oi][s][ti]
static void buildFlipMaskForOrigins(const int originsUsed[ORIGIN_USE], int originsCount) {
  for (int oi=0; oi<originsCount; oi++) {
    int o = originsUsed[oi];
    for (int ti=0; ti<TGT; ti++) {
      uint64_t addAt[TS];
      memset(addAt, 0, sizeof(addAt));
      for (int d=0; d<N; d++) {
        if (!validPair[o][d]) continue;
        if (s_ci[o][d][ti] > s_sq[o][d][ti]) continue;
        int16_t sq = s_sq[o][d][ti];
        int thr = (sq < 0 ? 0 : (int)sq + 1);
        if (thr <= TS-1) addAt[thr] |= (1ull << d);
      }
      uint64_t cur=0;
      for (int s=0; s<TS; s++) {
        cur |= addAt[s];
        flipMask[oi][s][ti] = cur;
      }
    }
  }
}

// ===== active origins per vertex (cache fp pointer) =====
struct ActOrigins {
  uint8_t cnt;
  uint64_t wo[ORIGIN_USE];
  const uint64_t* fp0[ORIGIN_USE]; // points to flipMask[oi][sidx][0]
};
static ActOrigins act[V];

static void buildActOrigins(const int16_t (*originLatest[ORIGIN_USE])[TS],
                            const uint64_t originW[ORIGIN_USE],
                            int originsCount) {
  for (int u=0; u<N*TS; u++) {
    int c = u/TS;
    int t = u%TS;
    uint8_t cnt=0;
    for (int oi=0; oi<originsCount; oi++) {
      int16_t s = originLatest[oi][c][t];
      if (s < 0) continue;
      act[u].wo[cnt]  = originW[oi];
      act[u].fp0[cnt] = &flipMask[oi][(int)s][0];
      cnt++;
    }
    act[u].cnt = cnt;
  }
}

// ===== edgeGain (faster due to flipMask layout) =====
static inline uint64_t edgeGainUV(int u, int vtx, int startTi) {
  uint64_t gain = 0;
  const ActOrigins& A = act[u];
  const uint64_t* rm = reachMask[vtx];
  uint64_t lastMask = ~0ull;
  uint64_t lastSum = 0;

  for (int k=0; k<(int)A.cnt; k++) {
    uint64_t wo = A.wo[k];
    const uint64_t* fp = A.fp0[k]; // fp[ti] is flipMask for this origin and sidx

    for (int ti=startTi; ti<TGT; ti++) {
      uint64_t m = fp[ti] & rm[ti];
      if (!m) continue;
      uint64_t sw;
      if (m == lastMask) sw = lastSum;
      else {
        sw = sumW_mask(m);
        lastMask = m;
        lastSum = sw;
      }
      gain += wo * sw;
    }
  }
  return gain;
}

static vector<FlightOut> restoreFlightsFromEnd(int endVtx, const int prevv[V]) {
  vector<FlightOut> revFlights;
  int cur = endVtx;
  while (cur != -1) {
    int p = prevv[cur];
    if (p == -1) break;
    int pc = p / TS, pt = p % TS;
    int cc = cur / TS, ct = cur % TS;
    if (pc != cc) revFlights.push_back(FlightOut{pc, cc, pt, ct});
    cur = p;
  }
  reverse(revFlights.begin(), revFlights.end());
  return revFlights;
}

// ===== top-2 DP routes for one plane (different end cities) =====
static vector<RouteCandidate> solveOnePlaneDPTopK(const vector<int>& startCities) {
  static __int128 dp[V];
  static int prevv[V];
  static long long dpSec[V];
  static int16_t dpMove[V];
  static int32_t dpPopDiv[V];

  const __int128 NEG = -((__int128)1 << 120);
  const long long NEG_SEC = numeric_limits<long long>::min() / 4;
  for (int i = 0; i < V; i++) {
    dp[i] = NEG;
    prevv[i] = -1;
    dpSec[i] = NEG_SEC;
    dpMove[i] = -1;
    dpPopDiv[i] = -1;
  }

  for (int c : startCities) {
    dp[c * TS] = 0;
    dpSec[c * TS] = 0;
    dpMove[c * TS] = 0;
    dpPopDiv[c * TS] = 0;
  }

  auto betterState = [&](int v, __int128 nv, long long ns, int16_t nm, int32_t np, int p) {
    if (nv != dp[v]) return nv > dp[v];
    if (ns != dpSec[v]) return ns > dpSec[v];
    if (nm != dpMove[v]) return nm > dpMove[v];
    if (np != dpPopDiv[v]) return np > dpPopDiv[v];
    return (prevv[v] < 0 || p < prevv[v]);
  };

  for (int t = 0; t < TS; t++) {
    for (int c = 0; c < N; c++) {
      int u = c * TS + t;
      __int128 cur = dp[u];
      if (cur == NEG) continue;

      // wait
      if (t + 1 < TS) {
        int v = u + 1;
        if (betterState(v, cur, dpSec[u], dpMove[u], dpPopDiv[u], u)) {
          dp[v] = cur;
          dpSec[v] = dpSec[u];
          dpMove[v] = dpMove[u];
          dpPopDiv[v] = dpPopDiv[u];
          prevv[v] = u;
        }
      }

      // moves
      int mcnt = (int)dpMoveCnt[u];
      const uint16_t* mv = dpMoveV[u];
      const uint8_t* ms = dpMoveStartTi[u];
      for (int mi = 0; mi < mcnt; mi++) {
        int v = (int)mv[mi];
        int st = (int)ms[mi];
        uint64_t g = edgeGainUV(u, v, st);
        __int128 nv = cur + (__int128)g;
        int toCity = v / TS;
        int at = v % TS;
        int popDiv = (int)(popW[toCity] / 1000);
        long long stepSec = (long long)gTieMove
                          + 1LL * gTiePopDiv * popDiv
                          + 1LL * gTieArr * at;
        long long ns = dpSec[u] + stepSec;
        int16_t nm = (int16_t)(dpMove[u] + 1);
        int32_t np = dpPopDiv[u] + popDiv;
        if (betterState(v, nv, ns, nm, np, u)) {
          dp[v] = nv;
          dpSec[v] = ns;
          dpMove[v] = nm;
          dpPopDiv[v] = np;
          prevv[v] = u;
        }
      }
    }
  }

  vector<RouteCandidate> out;
  out.reserve(gBranches);

  static __int128 cityBestVal[MAXN];
  static int cityBestVtx[MAXN];
  static long long cityBestSec[MAXN];
  static int16_t cityBestMove[MAXN];
  static int32_t cityBestPopDiv[MAXN];
  for (int city = 0; city < N; city++) {
    cityBestVal[city] = NEG;
    cityBestVtx[city] = -1;
    cityBestSec[city] = NEG_SEC;
    cityBestMove[city] = -1;
    cityBestPopDiv[city] = -1;
  }
  for (int v = 0; v < V; v++) {
    if (dp[v] == NEG) continue;
    int city = v / TS;
    if (dp[v] > cityBestVal[city] ||
        (dp[v] == cityBestVal[city] && (
          dpSec[v] > cityBestSec[city] ||
          (dpSec[v] == cityBestSec[city] && (
            dpMove[v] > cityBestMove[city] ||
            (dpMove[v] == cityBestMove[city] && (
              dpPopDiv[v] > cityBestPopDiv[city] ||
              (dpPopDiv[v] == cityBestPopDiv[city] &&
               (cityBestVtx[city] < 0 || v < cityBestVtx[city]))
            ))
          ))
        ))) {
      cityBestVal[city] = dp[v];
      cityBestVtx[city] = v;
      cityBestSec[city] = dpSec[v];
      cityBestMove[city] = dpMove[v];
      cityBestPopDiv[city] = dpPopDiv[v];
    }
  }

  bool usedEndCity[MAXN];
  memset(usedEndCity, 0, sizeof(usedEndCity));
  int selectedCities[MAXN];
  int selectedArr[MAXN];
  int selectedCnt = 0;
  for (int k = 0; k < gBranches; k++) {
    __int128 bestVal = NEG;
    int bestCity = -1;
    int bestVtx = -1;
    long long bestSec = NEG_SEC;
    int16_t bestMove = -1;
    int32_t bestPopDiv = -1;
    for (int city = 0; city < N; city++) {
      if (usedEndCity[city]) continue;
      int v = cityBestVtx[city];
      if (v < 0) continue;
      __int128 val = cityBestVal[city];
      long long sec = cityBestSec[city];
      if (gBranchMode == 1 && selectedCnt > 0) {
        double minD = 1e100;
        for (int i = 0; i < selectedCnt; i++) minD = min(minD, distMat[city][selectedCities[i]]);
        sec += (long long)llround(minD * gBranchDivW);
      } else if (gBranchMode == 2 && selectedCnt > 0) {
        int arr = v % TS;
        int minDt = TS;
        for (int i = 0; i < selectedCnt; i++) minDt = min(minDt, abs(arr - selectedArr[i]));
        sec += 1LL * gBranchDivW * minDt;
      }
      if (val > bestVal ||
          (val == bestVal && (sec > bestSec ||
            (sec == bestSec && (cityBestMove[city] > bestMove ||
              (cityBestMove[city] == bestMove && (cityBestPopDiv[city] > bestPopDiv ||
                (cityBestPopDiv[city] == bestPopDiv &&
                 (bestVtx < 0 || v < bestVtx))))))))) {
        bestVal = val;
        bestCity = city;
        bestVtx = v;
        bestSec = sec;
        bestMove = cityBestMove[city];
        bestPopDiv = cityBestPopDiv[city];
      }
    }
    if (bestCity < 0) break;
    usedEndCity[bestCity] = true;
    selectedCities[selectedCnt] = bestCity;
    selectedArr[selectedCnt] = bestVtx % TS;
    selectedCnt++;
    out.push_back(RouteCandidate{restoreFlightsFromEnd(bestVtx, prevv), bestVal});
  }

  return out;
}

static vector<vector<int>> buildCandidateDestinations(const vector<int>& popOrder) {
  // nearest + popular candidates, then deduplicated in ascending city index
  vector<vector<int>> candDest(N);
  for (int i=0;i<N;i++){
    vector<pair<double,int>> near;
    near.reserve(N-1);
    for (int j=0;j<N;j++){
      if (i==j) continue;
      near.push_back({distMat[i][j], j});
    }
    sort(near.begin(), near.end());

    vector<int> cand;
    cand.reserve(min(NEAR_CAND, N-1) + min(POP_CAND, N-1) + 4);

    int takeNear = min(NEAR_CAND, N-1);
    for (int k=0; k<(int)near.size() && (int)cand.size()<takeNear; k++){
      cand.push_back(near[k].second);
    }

    int takePop = min(POP_CAND, N-1);
    int addedPop = 0;
    for (int k=0; k<N && addedPop<takePop; k++){
      int j = popOrder[k];
      if (j==i) continue;
      cand.push_back(j);
      addedPop++;
    }

    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    candDest[i]=cand;
  }
  return candDest;
}

static vector<int> buildStartCities(const vector<int>& popOrder) {
  vector<int> startCities;
  for (int i=0;i<min(START_USE, N); i++) {
    startCities.push_back(popOrder[i]);
  }
  return startCities;
}

static void buildDpTransitions(const vector<vector<int>>& candDest) {
  // Keep candidate order to preserve exact DP tie behavior.
  for (int c=0; c<N; c++) {
    const auto& cd = candDest[c];
    for (int t=0; t<TS; t++) {
      int u = c*TS + t;
      uint8_t cnt = 0;
      for (int j: cd) {
        int at = t + durSlot[c][j];
        if (at >= TS) continue;
        dpMoveV[u][cnt] = (uint16_t)(j*TS + at);
        dpMoveStartTi[u][cnt] = (uint8_t)firstTiTime[at];
        cnt++;
      }
      dpMoveCnt[u] = cnt;
    }
  }
}

static int buildOrigins(const vector<int>& popOrder,
                        int originsUsed[ORIGIN_USE],
                        uint64_t originW[ORIGIN_USE],
                        const int16_t (*originLatest[ORIGIN_USE])[TS]) {
  int originsCount = 0;
  for (int i=0; i<min(ORIGIN_USE, N); i++) {
    int city = popOrder[i];
    originsUsed[originsCount] = city;
    originW[originsCount] = (uint64_t)popW[city];
    originLatest[originsCount] = latestCi[city];
    originsCount++;
  }
  return originsCount;
}

// ===== debug score =====
static long long evalScoreEstimate() {
  __int128 vci=0, vsq=0;
  for (int o=0;o<N;o++){
    for (int d=0;d<N;d++){
      if (!validPair[o][d]) continue;
      __int128 ww = (__int128)popW[o] * (__int128)popW[d];
      for (int ti=0;ti<TGT;ti++){
        if (s_ci[o][d][ti] > s_sq[o][d][ti]) vci += ww;
        else vsq += ww;
      }
    }
  }
  if (vci+vsq==0) return 0;
  long double S = (long double)vci / (long double)(vci+vsq);
  return (long long)floor(1e6L * S + 1e-12L);
}

struct BeamState {
  CSRAdj<20000> ci;
  vector<vector<FlightOut>> routes;
  __int128 score;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  // Skip UTF-8 BOM if present in local test files.
  if (cin.peek() == 0xEF) {
    char b1 = 0, b2 = 0, b3 = 0;
    cin.get(b1);
    cin.get(b2);
    cin.get(b3);
    if (!(b1 == (char)0xEF && b2 == (char)0xBB && b3 == (char)0xBF)) {
      cin.clear();
    }
  }

  {
    int v;
    if (parseEnvInt("SC_BEAM_WIDTH", v) && v >= 1) gBeamWidth = v;
    if (parseEnvInt("SC_BRANCHES", v) && v >= 1) gBranches = v;
    if (parseEnvInt("SC_TIE_MOVE", v)) gTieMove = v;
    if (parseEnvInt("SC_TIE_POPDIV", v)) gTiePopDiv = v;
    if (parseEnvInt("SC_TIE_ARR", v)) gTieArr = v;
    if (parseEnvInt("SC_BRANCH_MODE", v)) gBranchMode = v;
    if (parseEnvInt("SC_BRANCH_DIVW", v)) gBranchDivW = v;
    if (parseEnvInt("SC_SCORE_MODE", v)) gScoreMode = v;
    if (parseEnvInt("SC_BEAM_GAP", v)) gBeamGap = v;
    if (parseEnvInt("SC_VERBOSE_STEP", v)) gVerboseStep = v;
    if (parseEnvInt("SC_EVAL_FLIGHT_W", v)) gEvalFlightW = v;
    if (parseEnvInt("SC_EVAL_POPDIV_W", v)) gEvalPopDivW = v;
    if (parseEnvInt("SC_EVAL_LATEARR_W", v)) gEvalLateArrW = v;
  }

  cin >> N >> R;
  vector<int> xs(N), ys(N);
  for (int i=0;i<N;i++) cin >> xs[i] >> ys[i] >> popW[i];

  for (int i=0;i<TGT;i++){
    int minute = 11*60 + 30*i;
    tgtIdx[i] = timeToIdx(minute);
  }
  {
    int cur=0;
    for (int t=0;t<TS;t++){
      while (cur<TGT && tgtIdx[cur] < t) cur++;
      firstTiTime[t] = cur;
    }
  }

  double thr = 0.25 * (double)R;
  for (int i=0;i<N;i++){
    for (int j=0;j<N;j++){
      double dx = (double)xs[i]-xs[j];
      double dy = (double)ys[i]-ys[j];
      double d = sqrt(dx*dx + dy*dy);
      distMat[i][j]=d;
      validPair[i][j] = (d >= thr);
      if (i==j) durSlot[i][j]=0;
      else {
        double raw = 60.0 * d / 800.0 + 40.0;
        int q = (int)ceil(raw / 5.0 - 1e-12);
        durSlot[i][j] = q; // in 5-min slots
      }
    }
  }

  buildWeightTables(popW);

  int M;
  cin >> M;
  sqAdj.init();
  for (int k=0;k<M;k++){
    int a,b;
    string ss, tt;
    cin >> a >> ss >> b >> tt;
    --a; --b;
    int s = timeToIdx(parseTimeStr(ss));
    int t = timeToIdx(parseTimeStr(tt));
    sqAdj.addEdge(a*TS + s, b, t);
  }
  sqAdj.build();

  int K;
  cin >> K;
  (void)K;

  ciAdj.init();

  // Square: earliest/latest/targets
  buildEarliestAndLatest(sqAdj, earliestSq, latestSq);
  buildTargetsFromLatest(latestSq, s_sq);

  // population order
  vector<int> popOrder(N);
  iota(popOrder.begin(), popOrder.end(), 0);
  sort(popOrder.begin(), popOrder.end(), [&](int a,int b){ return popW[a]>popW[b]; });

  vector<vector<int>> candDest = buildCandidateDestinations(popOrder);
  vector<int> startCities = buildStartCities(popOrder);
  buildDpTransitions(candDest);

  // origins: all cities (pop order)
  int originsUsed[ORIGIN_USE];
  uint64_t originW[ORIGIN_USE];
  const int16_t (*originLatest[ORIGIN_USE])[TS];
  int originsCount = buildOrigins(popOrder, originsUsed, originW, originLatest);

  vector<BeamState> beam;
  beam.reserve(gBeamWidth);
  BeamState root;
  root.ci.init();
  root.routes.reserve(K_FIXED);
  root.score = 0;
  beam.push_back(move(root));

  for (int plane = 0; plane < K_FIXED; plane++) {
    vector<BeamState> nextBeam;
    nextBeam.reserve(gBeamWidth * gBranches);

    for (auto& st : beam) {
      st.ci.build();

      buildEarliestAndLatest(st.ci, earliestCi, latestCi);
      buildTargetsFromLatest(latestCi, s_ci);
      long long parentTrueScore = 0;
      if (gScoreMode == 1) parentTrueScore = evalScoreEstimate();
      buildReachMaskFromEarliestFast(earliestCi);
      buildFlipMaskForOrigins(originsUsed, originsCount);
      buildActOrigins(originLatest, originW, originsCount);

      auto candRoutes = solveOnePlaneDPTopK(startCities);
      if (candRoutes.empty()) candRoutes.push_back(RouteCandidate{{}, 0});

      for (int i = 0; i < (int)candRoutes.size(); i++) {
        BeamState child = st;
        if (gScoreMode == 1) {
          child.score = (__int128)parentTrueScore + candRoutes[i].value;
        } else {
          child.score = st.score + candRoutes[i].value;
        }
        child.score += (__int128)routeEvalBonus(candRoutes[i].flights);
        child.routes.push_back(candRoutes[i].flights);
        for (const auto& f : candRoutes[i].flights) {
          int uV = f.a * TS + f.dep_t;
          child.ci.addEdge(uV, f.b, f.arr_t);
        }
        nextBeam.push_back(move(child));
      }
    }

    if (nextBeam.empty()) {
      cerr << "[beam step " << (plane + 1) << "] no candidates\n";
      break;
    }

    sort(nextBeam.begin(), nextBeam.end(), [](const BeamState& a, const BeamState& b) {
      return a.score > b.score;
    });
    if ((int)nextBeam.size() > gBeamWidth) nextBeam.resize(gBeamWidth);
    if (gBeamGap >= 0 && !nextBeam.empty()) {
      __int128 thr = nextBeam[0].score - (__int128)gBeamGap;
      int keep = 0;
      while (keep < (int)nextBeam.size() && nextBeam[keep].score >= thr) keep++;
      if (keep <= 0) keep = 1;
      if (keep < (int)nextBeam.size()) nextBeam.resize(keep);
    }
    beam.swap(nextBeam);

    if (gVerboseStep) {
      cerr << "[beam step " << (plane + 1) << "] beam_size=" << beam.size()
           << " best_flights=" << beam[0].routes.back().size() << "\n";
    }
  }

  BeamState best = beam[0];
  vector<vector<FlightOut>> routes = best.routes;
  if ((int)routes.size() < K_FIXED) routes.resize(K_FIXED);
  auto buildCiFromRoutes = [&](const vector<vector<FlightOut>>& rs, CSRAdj<20000>& outCi) {
    outCi.init();
    for (const auto& r : rs) {
      for (const auto& f : r) outCi.addEdge(f.a * TS + f.dep_t, f.b, f.arr_t);
    }
  };
  auto evalCiScore = [&](CSRAdj<20000>& ci) -> long long {
    ci.build();
    buildEarliestAndLatest(ci, earliestCi, latestCi);
    buildTargetsFromLatest(latestCi, s_ci);
    return evalScoreEstimate();
  };
  auto sameRoute = [&](const vector<FlightOut>& a, const vector<FlightOut>& b) -> bool {
    if (a.size() != b.size()) return false;
    for (int i = 0; i < (int)a.size(); i++) {
      if (a[i].a != b[i].a || a[i].b != b[i].b || a[i].dep_t != b[i].dep_t || a[i].arr_t != b[i].arr_t) return false;
    }
    return true;
  };

  buildCiFromRoutes(routes, ciAdj);
  long long bestTrueScore = evalCiScore(ciAdj);

  // Small coordinate improvement: re-optimize weak (short) routes a few times.
  {
    static constexpr int REFINE_TRIALS = 3;
    bool usedPlane[K_FIXED];
    memset(usedPlane, 0, sizeof(usedPlane));
    for (int tr = 0; tr < REFINE_TRIALS; tr++) {
      int targetPlane = -1;
      long long worstBonus = (1LL << 60);
      int bestLen = INT_MAX;
      for (int p = 0; p < K_FIXED; p++) {
        if (usedPlane[p]) continue;
        long long b = routeEvalBonus(routes[p]);
        int len = (int)routes[p].size();
        if (b < worstBonus || (b == worstBonus && len < bestLen)) {
          worstBonus = b;
          bestLen = len;
          targetPlane = p;
        }
      }
      if (targetPlane < 0) break;
      usedPlane[targetPlane] = true;

      vector<vector<FlightOut>> without = routes;
      without[targetPlane].clear();
      CSRAdj<20000> ciWithout;
      buildCiFromRoutes(without, ciWithout);
      evalCiScore(ciWithout);
      buildReachMaskFromEarliestFast(earliestCi);
      buildFlipMaskForOrigins(originsUsed, originsCount);
      buildActOrigins(originLatest, originW, originsCount);
      auto cand = solveOnePlaneDPTopK(startCities);
      if (!cand.empty() && !sameRoute(cand[0].flights, routes[targetPlane])) {
        auto old = routes[targetPlane];
        routes[targetPlane] = cand[0].flights;
        CSRAdj<20000> ciTry;
        buildCiFromRoutes(routes, ciTry);
        long long scTry = evalCiScore(ciTry);
        if (scTry > bestTrueScore) {
          bestTrueScore = scTry;
          ciAdj = move(ciTry);
        } else {
          routes[targetPlane] = move(old);
        }
      }
    }
  }

  // final debug
  cerr << "[final estimated score] " << bestTrueScore << "\n";

  // output
  for (int p=0;p<K_FIXED;p++){
    cout << routes[p].size() << "\n";
    for (auto &f: routes[p]) {
      cout << (f.a+1) << " " << fmtTimeIdx(f.dep_t) << " "
           << (f.b+1) << " " << fmtTimeIdx(f.arr_t) << "\n";
    }
  }
  return 0;
}