#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;

struct City {
    int x, y;
    ll w;
};

struct Flight {
    int a, b;
    int s, t;
};

struct PlanePlan {
    vector<int> route;
    int offset = 0;
    int duration = 0;
};

struct DemandTerm {
    int src, dst;
    long double w;
    array<int, 21> sq;
};

constexpr int START_HOUR = 6;
constexpr int END_HOUR = 21;
constexpr int SLOT_MIN = 5;
constexpr int MAX_SLOT = (END_HOUR - START_HOUR) * 60 / SLOT_MIN; // 180
constexpr int TARGET_CNT = 21;
constexpr int TARGET_START = (11 - START_HOUR) * 60 / SLOT_MIN; // 60
constexpr int TARGET_STEP = 30 / SLOT_MIN;                      // 6
constexpr int NEG_INF = -1e9;

int parseTimeToSlot(const string &s) {
    auto pos = s.find(':');
    int hh = stoi(s.substr(0, pos));
    int mm = stoi(s.substr(pos + 1));
    return (hh * 60 + mm - START_HOUR * 60) / SLOT_MIN;
}

string slotToTime(int slot) {
    int total = START_HOUR * 60 + slot * SLOT_MIN;
    int hh = total / 60;
    int mm = total % 60;
    char buf[16];
    snprintf(buf, sizeof(buf), "%02d:%02d", hh, mm);
    return string(buf);
}

int calcDurationSlot(const City &c1, const City &c2) {
    double dx = double(c1.x) - double(c2.x);
    double dy = double(c1.y) - double(c2.y);
    double d = sqrt(dx * dx + dy * dy);
    double minutes = 60.0 * d / 800.0 + 40.0;
    return (int)ceil(minutes / 5.0 - 1e-12);
}

int routeDuration(const vector<int> &route, const vector<vector<int>> &dur) {
    int total = 0;
    for(int i = 1; i < (int)route.size(); ++i) {
        if(route[i - 1] == route[i])
            return MAX_SLOT + 1;
        total += dur[route[i - 1]][route[i]];
        if(total > MAX_SLOT)
            return total;
    }
    return total;
}

void normalizePlane(PlanePlan &p, const vector<vector<int>> &dur) {
    if(p.route.empty())
        p.route.push_back(0);
    vector<int> fixed;
    fixed.reserve(p.route.size());
    fixed.push_back(p.route[0]);
    for(int i = 1; i < (int)p.route.size(); ++i) {
        if(p.route[i] != p.route[i - 1])
            fixed.push_back(p.route[i]);
    }
    p.route.swap(fixed);
    if(p.route.empty())
        p.route.push_back(0);
    p.duration = routeDuration(p.route, dur);
    while(p.duration > MAX_SLOT && (int)p.route.size() > 1) {
        p.route.pop_back();
        p.duration = routeDuration(p.route, dur);
    }
    int lim = max(0, MAX_SLOT - p.duration);
    p.offset = min(max(0, p.offset), lim);
}

void appendPlaneFlights(const PlanePlan &p, const vector<vector<int>> &dur, vector<Flight> &out) {
    int tm = p.offset;
    for(int i = 1; i < (int)p.route.size(); ++i) {
        int a = p.route[i - 1];
        int b = p.route[i];
        int nt = tm + dur[a][b];
        out.push_back({a, b, tm, nt});
        tm = nt;
    }
}

vector<Flight> flattenPlans(const vector<PlanePlan> &plans, const vector<vector<int>> &dur) {
    vector<Flight> flights;
    for(const auto &p : plans)
        appendPlaneFlights(p, dur, flights);
    return flights;
}

struct ScoreEvaluator {
    int N;
    uint64_t allMask;

    explicit ScoreEvaluator(int n) : N(n) {
        allMask = (N == 64 ? ~0ULL : ((1ULL << N) - 1));
    }

    vector<vector<Flight>> buildByStart(const vector<Flight> &flights, int target) const {
        vector<vector<Flight>> byStart(target + 1);
        for(const auto &f : flights) {
            if(f.s < 0 || f.s > target || f.t < 0 || f.t > target)
                continue;
            byStart[f.s].push_back(f);
        }
        return byStart;
    }

    vector<vector<int>> latestMatrixForTarget(const vector<vector<Flight>> &byStart, int target) const {
        vector<vector<uint64_t>> reach(target + 1, vector<uint64_t>(N, 0ULL));
        for(int c = 0; c < N; ++c)
            reach[target][c] = (1ULL << c);

        for(int tm = target - 1; tm >= 0; --tm) {
            for(int c = 0; c < N; ++c)
                reach[tm][c] = reach[tm + 1][c];
            for(const auto &f : byStart[tm]) {
                reach[tm][f.a] |= reach[f.t][f.b];
            }
        }

        vector<vector<int>> latest(N, vector<int>(N, NEG_INF));
        for(int src = 0; src < N; ++src) {
            uint64_t rem = allMask;
            for(int tm = target; tm >= 0 && rem; --tm) {
                uint64_t m = reach[tm][src] & rem;
                while(m) {
                    int dst = __builtin_ctzll(m);
                    latest[src][dst] = tm;
                    rem &= ~(1ULL << dst);
                    m &= (m - 1);
                }
            }
        }
        return latest;
    }

    vector<vector<vector<int>>> precomputeSqBest(const vector<Flight> &sqFlights) const {
        vector<vector<vector<int>>> sqBest(TARGET_CNT, vector<vector<int>>(N, vector<int>(N, NEG_INF)));
        for(int k = 0; k < TARGET_CNT; ++k) {
            int target = TARGET_START + TARGET_STEP * k;
            auto byStart = buildByStart(sqFlights, target);
            sqBest[k] = latestMatrixForTarget(byStart, target);
        }
        return sqBest;
    }

    vector<vector<vector<int>>> precomputeAllLatest(const vector<Flight> &flights) const {
        vector<vector<Flight>> allByStart(MAX_SLOT + 1);
        for(const auto &f : flights) {
            if(0 <= f.s && f.s <= MAX_SLOT && 0 <= f.t && f.t <= MAX_SLOT)
                allByStart[f.s].push_back(f);
        }

        vector<vector<vector<int>>> allLatest(MAX_SLOT + 1, vector<vector<int>>(N, vector<int>(N, NEG_INF)));
        for(int deadline = 0; deadline <= MAX_SLOT; ++deadline) {
            vector<vector<uint64_t>> reach(deadline + 1, vector<uint64_t>(N, 0ULL));
            for(int c = 0; c < N; ++c)
                reach[deadline][c] = (1ULL << c);

            for(int tm = deadline - 1; tm >= 0; --tm) {
                for(int c = 0; c < N; ++c)
                    reach[tm][c] = reach[tm + 1][c];
                for(const auto &f : allByStart[tm]) {
                    if(f.t <= deadline)
                        reach[tm][f.a] |= reach[f.t][f.b];
                }
            }

            for(int src = 0; src < N; ++src) {
                uint64_t rem = allMask;
                for(int tm = deadline; tm >= 0 && rem; --tm) {
                    uint64_t m = reach[tm][src] & rem;
                    while(m) {
                        int dst = __builtin_ctzll(m);
                        allLatest[deadline][src][dst] = tm;
                        rem &= ~(1ULL << dst);
                        m &= (m - 1);
                    }
                }
            }
        }
        return allLatest;
    }

    double score(
        const vector<Flight> &ciFlights,
        const vector<DemandTerm> &demands) const {
        long double vSq = 0.0L, vCi = 0.0L;

        for(int k = 0; k < TARGET_CNT; ++k) {
            int target = TARGET_START + TARGET_STEP * k;
            auto byStart = buildByStart(ciFlights, target);
            auto latest = latestMatrixForTarget(byStart, target);

            for(const auto &d : demands) {
                if(d.sq[k] < latest[d.src][d.dst])
                    vCi += d.w;
                else
                    vSq += d.w;
            }
        }

        long double den = vSq + vCi;
        if(den <= 0.0L)
            return 0.0;
        return (double)(vCi / den);
    }
};

PlanePlan buildCyclicPlan(
    const vector<int> &cycle,
    int offset,
    const vector<vector<int>> &dur) {
    PlanePlan p;
    if(cycle.empty())
        return p;

    p.route.push_back(cycle[0]);
    p.offset = offset;

    int tm = offset;
    int cur = cycle[0];
    int idx = 1 % (int)cycle.size();

    while(true) {
        int nxt = cycle[idx];
        if(nxt == cur)
            break;
        int nt = tm + dur[cur][nxt];
        if(nt > MAX_SLOT)
            break;
        p.route.push_back(nxt);
        tm = nt;
        cur = nxt;
        idx = (idx + 1) % (int)cycle.size();
    }

    p.duration = tm - offset;
    normalizePlane(p, dur);
    return p;
}

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

    int N, R;
    cin >> N >> R;
    vector<City> cities(N);
    for(int i = 0; i < N; ++i)
        cin >> cities[i].x >> cities[i].y >> cities[i].w;

    int M;
    cin >> M;
    vector<Flight> sqFlights(M);
    for(int i = 0; i < M; ++i) {
        int a, b;
        string ss, tt;
        cin >> a >> ss >> b >> tt;
        --a;
        --b;
        sqFlights[i] = {a, b, parseTimeToSlot(ss), parseTimeToSlot(tt)};
    }

    int K;
    cin >> K;

    vector<vector<int>> dur(N, vector<int>(N, 0));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j)
            if(i != j)
                dur[i][j] = calcDurationSlot(cities[i], cities[j]);
    }

    vector<vector<long double>> pairWeight(N, vector<long double>(N, 0.0L));
    double threshold = 0.25 * R;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            double dx = double(cities[i].x) - double(cities[j].x);
            double dy = double(cities[i].y) - double(cities[j].y);
            double d = sqrt(dx * dx + dy * dy);
            if(d + 1e-12 >= threshold) {
                pairWeight[i][j] = (long double)cities[i].w * (long double)cities[j].w;
            }
        }
    }

    ScoreEvaluator evaluator(N);
    auto sqBest = evaluator.precomputeSqBest(sqFlights); // [k][src][dst]

    vector<DemandTerm> demands;
    demands.reserve(N * N);
    for(int src = 0; src < N; ++src) {
        for(int dst = 0; dst < N; ++dst) {
            if(pairWeight[src][dst] == 0.0L)
                continue;
            DemandTerm d;
            d.src = src;
            d.dst = dst;
            d.w = pairWeight[src][dst];
            for(int k = 0; k < TARGET_CNT; ++k)
                d.sq[k] = sqBest[k][src][dst];
            demands.push_back(d);
        }
    }
    vector<vector<int>> demandId(N, vector<int>(N, -1));
    for(int i = 0; i < (int)demands.size(); ++i)
        demandId[demands[i].src][demands[i].dst] = i;

    vector<long double> cityScore(N, 0.0L);
    for(int i = 0; i < N; ++i) {
        long double s = (long double)cities[i].w * 1e6L;
        for(int j = 0; j < N; ++j)
            s += pairWeight[i][j] + pairWeight[j][i];
        cityScore[i] = max((long double)1.0, s);
    }

    vector<int> cityOrd(N);
    iota(cityOrd.begin(), cityOrd.end(), 0);
    sort(cityOrd.begin(), cityOrd.end(), [&](int a, int b) {
        return cityScore[a] > cityScore[b];
    });

    long double totalDen = 0.0L;
    for(const auto &d : demands)
        totalDen += d.w;
    totalDen *= (long double)TARGET_CNT;

    double bestScoreAll = -1.0;
    int bestTrial = -1;
    vector<vector<Flight>> bestPlaneFlights;
    auto baseLatestAll = evaluator.precomputeAllLatest({});
    mt19937_64 rng(123456789ULL);
    const double TL = 0.85;
    const int maxLegPerPlane = 14;
    auto begin = chrono::steady_clock::now();

    auto makeSeedOrder = [&](int token) {
        vector<int> seedOrder = cityOrd;
        int mode = token % 4;
        if(mode == 0) {
            int shift = (token * 7) % N;
            rotate(seedOrder.begin(), seedOrder.begin() + shift, seedOrder.end());
        } else if(mode == 1) {
            reverse(seedOrder.begin(), seedOrder.end());
            int shift = (token * 5) % N;
            rotate(seedOrder.begin(), seedOrder.begin() + shift, seedOrder.end());
        } else if(mode == 2) {
            int top = min(N, max(12, K * 2));
            shuffle(seedOrder.begin(), seedOrder.begin() + top, rng);
            int shift = (int)(rng() % N);
            rotate(seedOrder.begin(), seedOrder.begin() + shift, seedOrder.end());
        } else {
            int top = min(N, max(20, K * 3));
            shuffle(seedOrder.begin(), seedOrder.begin() + top, rng);
            int rest = min(N, top + 10);
            if(top < rest)
                shuffle(seedOrder.begin() + top, seedOrder.begin() + rest, rng);
            int shift = (int)(rng() % N);
            rotate(seedOrder.begin(), seedOrder.begin() + shift, seedOrder.end());
        }
        return seedOrder;
    };

    auto flattenPlaneFlights = [&](const vector<vector<Flight>> &pf) {
        vector<Flight> flights;
        for(const auto &v : pf)
            flights.insert(flights.end(), v.begin(), v.end());
        return flights;
    };

    auto applyFlightToLatestAll = [&](vector<vector<vector<int>>> &latestAll, int a, int b, int dep, int arr) {
        const auto &depMat = latestAll[dep];
        for(int target = arr; target <= MAX_SLOT; ++target) {
            auto &targetMat = latestAll[target];

            array<int, 47> dstList{};
            int dstCnt = 0;
            for(int dst = 0; dst < N; ++dst) {
                if(targetMat[b][dst] >= arr)
                    dstList[dstCnt++] = dst;
            }
            if(dstCnt == 0)
                continue;

            for(int src = 0; src < N; ++src) {
                int pre = depMat[src][a];
                if(pre == NEG_INF)
                    continue;
                for(int i = 0; i < dstCnt; ++i) {
                    int dst = dstList[i];
                    if(pre > targetMat[src][dst])
                        targetMat[src][dst] = pre;
                }
            }
        }
    };

    auto calcCiFromLatest = [&](const vector<vector<vector<int>>> &latestAll) {
        long double ci = 0.0L;
        for(int k = 0; k < TARGET_CNT; ++k) {
            int target = TARGET_START + TARGET_STEP * k;
            for(const auto &d : demands) {
                if(d.sq[k] < latestAll[target][d.src][d.dst])
                    ci += d.w;
            }
        }
        return ci;
    };

    auto calcDeltaCiEdge = [&](int a, int b, int dep, int arr, const vector<vector<vector<int>>> &latestAll) {
        long double deltaCi = 0.0L;
        const auto &depMat = latestAll[dep];
        array<int, 47> preBySrc{};
        array<int, 47> activeSrc{};
        int activeSrcCnt = 0;
        for(int src = 0; src < N; ++src)
            if((preBySrc[src] = depMat[src][a]) != NEG_INF)
                activeSrc[activeSrcCnt++] = src;
        if(activeSrcCnt == 0)
            return 0.0L;

        int startK = 0;
        if(arr > TARGET_START) {
            startK = (arr - TARGET_START + TARGET_STEP - 1) / TARGET_STEP;
            if(startK < 0)
                startK = 0;
            if(startK > TARGET_CNT)
                startK = TARGET_CNT;
        }

        array<array<int, 47>, TARGET_CNT> addDst{};
        array<int, TARGET_CNT> addCnt{};
        for(int dst = 0; dst < N; ++dst) {
            int firstK = TARGET_CNT;
            for(int k = startK; k < TARGET_CNT; ++k) {
                int target = TARGET_START + TARGET_STEP * k;
                if(latestAll[target][b][dst] >= arr) {
                    firstK = k;
                    break;
                }
            }
            if(firstK < TARGET_CNT)
                addDst[firstK][addCnt[firstK]++] = dst;
        }

        array<int, 47> activeDst{};
        int activeDstCnt = 0;
        for(int k = startK; k < TARGET_CNT; ++k) {
            for(int i = 0; i < addCnt[k]; ++i)
                activeDst[activeDstCnt++] = addDst[k][i];
            if(activeDstCnt == 0)
                continue;

            int target = TARGET_START + TARGET_STEP * k;
            const auto &targetMat = latestAll[target];

            for(int si = 0; si < activeSrcCnt; ++si) {
                int src = activeSrc[si];
                int pre = preBySrc[src];
                for(int di = 0; di < activeDstCnt; ++di) {
                    int dst = activeDst[di];
                    int idx2 = demandId[src][dst];
                    if(idx2 < 0)
                        continue;
                    const auto &d = demands[idx2];
                    int oldCi = targetMat[src][dst];
                    if(pre <= oldCi)
                        continue;
                    if(d.sq[k] < pre && !(d.sq[k] < oldCi))
                        deltaCi += d.w;
                }
            }
        }
        return deltaCi;
    };

    auto extendGreedy = [&](vector<vector<Flight>> &planeFlights,
                            vector<int> &headCity,
                            vector<int> &headTime,
                            vector<int> &legCount,
                            vector<vector<vector<int>>> &latestAll,
                            long double &currentCi,
                            double &currentScore,
                            int unlockPlane) {
        int maxTotalOps = K * maxLegPerPlane;
        for(int op = 0; op < maxTotalOps; ++op) {
            vector<tuple<int, int, int, int>> ops; // plane, from, dep, arr
            ops.reserve(K * N);

            for(int p = 0; p < K; ++p) {
                if(unlockPlane >= 0 && p != unlockPlane)
                    continue;
                if(legCount[p] >= maxLegPerPlane)
                    continue;
                int b = headCity[p];
                int arr = headTime[p];

                for(int a = 0; a < N; ++a) {
                    if(a == b)
                        continue;
                    int dep = arr - dur[a][b];
                    if(dep < 0)
                        continue;
                    ops.emplace_back(p, a, dep, arr);
                }
            }

            if(ops.empty())
                break;
            double bestScore = currentScore;
            long double bestDeltaCi = 0.0L;
            int bestPlane = -1, bestFrom = -1, bestDep = -1, bestArr = -1;

            for(const auto &[p, a, dep, arr] : ops) {
                int b = headCity[p];
                long double deltaCi = calcDeltaCiEdge(a, b, dep, arr, latestAll);

                double s = (totalDen > 0.0L ? (double)((currentCi + deltaCi) / totalDen) : 0.0);
                if(s > bestScore || (s == bestScore && deltaCi > bestDeltaCi)) {
                    bestScore = s;
                    bestDeltaCi = deltaCi;
                    bestPlane = p;
                    bestFrom = a;
                    bestDep = dep;
                    bestArr = arr;
                }
            }

            if(bestPlane < 0)
                break;

            int b = headCity[bestPlane];
            planeFlights[bestPlane].insert(planeFlights[bestPlane].begin(), {bestFrom, b, bestDep, bestArr});
            headCity[bestPlane] = bestFrom;
            headTime[bestPlane] = bestDep;
            legCount[bestPlane]++;
            applyFlightToLatestAll(latestAll, bestFrom, b, bestDep, bestArr);
            currentCi += bestDeltaCi;
            currentScore = (totalDen > 0.0L ? (double)(currentCi / totalDen) : 0.0);
        }
    };

    auto buildPlaneByDP = [&](int seedCity, const vector<vector<vector<int>>> &latestAll) {
        static constexpr long double NEG = -1e100L;
        static array<array<array<long double, MAX_SLOT + 2>, 47>, 47> edgeDiff;
        static array<array<array<long double, MAX_SLOT + 1>, 47>, 47> edgeGain;
        static array<array<long double, MAX_SLOT + 1>, 47> dp;
        static array<array<int, MAX_SLOT + 1>, 47> nxt;

        for(int u = 0; u < N; ++u)
            for(int v = 0; v < N; ++v) {
                edgeDiff[u][v].fill(0.0L);
                edgeGain[u][v].fill(0.0L);
            }

        for(int u = 0; u < N; ++u) {
            for(int dst = 0; dst < N; ++dst) {
                if(pairWeight[u][dst] == 0.0L)
                    continue;
                for(int k = 0; k < TARGET_CNT; ++k) {
                    int target = TARGET_START + TARGET_STEP * k;
                    int r_s = sqBest[k][u][dst];
                    int c_s = latestAll[target][u][dst];
                    if(c_s > r_s)
                        continue;
                    int min_s = max(0, r_s + 1);
                    for(int v = 0; v < N; ++v) {
                        if(u == v)
                            continue;
                        int max_t = (v == dst ? target : latestAll[target][v][dst]);
                        if(max_t < 0)
                            continue;
                        int max_s = min(MAX_SLOT - dur[u][v], max_t - dur[u][v]);
                        if(min_s > max_s)
                            continue;
                        edgeDiff[u][v][min_s] += pairWeight[u][dst];
                        if(max_s + 1 <= MAX_SLOT)
                            edgeDiff[u][v][max_s + 1] -= pairWeight[u][dst];
                    }
                }
            }
        }

        for(int u = 0; u < N; ++u) {
            for(int v = 0; v < N; ++v) {
                long double cur = 0.0L;
                for(int s = 0; s <= MAX_SLOT; ++s) {
                    cur += edgeDiff[u][v][s];
                    edgeGain[u][v][s] = cur;
                }
            }
        }

        for(int u = 0; u < N; ++u) {
            dp[u].fill(0.0L);
            nxt[u].fill(-1);
        }
        for(int t = MAX_SLOT; t >= 0; --t) {
            for(int u = 0; u < N; ++u) {
                if(t + 1 <= MAX_SLOT) {
                    dp[u][t] = dp[u][t + 1];
                    nxt[u][t] = -1; // wait
                } else {
                    dp[u][t] = 0.0L;
                    nxt[u][t] = -1;
                }
                for(int v = 0; v < N; ++v) {
                    if(u == v)
                        continue;
                    int nt = t + dur[u][v];
                    if(nt > MAX_SLOT)
                        continue;
                    long double cand = edgeGain[u][v][t] + dp[v][nt];
                    if(cand > dp[u][t]) {
                        dp[u][t] = cand;
                        nxt[u][t] = v;
                    }
                }
            }
        }

        int bestCity = seedCity;
        long double bestVal = dp[seedCity][0];
        for(int u = 0; u < N; ++u) {
            if(dp[u][0] > bestVal) {
                bestVal = dp[u][0];
                bestCity = u;
            }
        }

        vector<Flight> path;
        int u = bestCity, t = 0;
        while(t <= MAX_SLOT) {
            int v = nxt[u][t];
            if(v < 0)
                t++;
            else {
                int nt = t + dur[u][v];
                path.push_back({u, v, t, nt});
                t = nt;
                u = v;
            }
        }
        return path;
    };

    vector<vector<Flight>> currentPlaneFlights(K);
    vector<int> currentHeadCity(K), currentHeadTime(K), currentLegCount(K, 0);
    auto seedOrder = makeSeedOrder(0);
    vector<vector<vector<int>>> latestAll = baseLatestAll;
    const int DP_INIT_PLANES = K;
    for(int p = 0; p < K; ++p) {
        int c = seedOrder[p % N];
        bool useDp = (p < DP_INIT_PLANES);
        if(useDp) {
            auto flights = buildPlaneByDP(c, latestAll);
            currentPlaneFlights[p] = flights;
            currentLegCount[p] = (int)flights.size();
            if(flights.empty()) {
                currentHeadCity[p] = c;
                currentHeadTime[p] = MAX_SLOT;
            } else {
                currentHeadCity[p] = flights[0].a;
                currentHeadTime[p] = flights[0].s;
                for(const auto &f : flights)
                    applyFlightToLatestAll(latestAll, f.a, f.b, f.s, f.t);
            }
        } else {
            currentHeadCity[p] = c;
            currentHeadTime[p] = MAX_SLOT;
            currentLegCount[p] = 0;
        }
    }
    long double currentCi = calcCiFromLatest(latestAll);
    double currentScore = (totalDen > 0.0L ? (double)(currentCi / totalDen) : 0.0);

    bestPlaneFlights = currentPlaneFlights;
    bestScoreAll = evaluator.score(flattenPlaneFlights(bestPlaneFlights), demands);
    bestTrial = 0;
    int initFlightCnt = 0;
    for(const auto &v : bestPlaneFlights)
        initFlightCnt += (int)v.size();
    cerr << fixed << setprecision(12)
         << "iter=0 score=" << bestScoreAll
         << " flights=" << initFlightCnt << '\n';

    int iter = 1;
    while(true) {
        double elapsed = chrono::duration<double>(chrono::steady_clock::now() - begin).count();
        if(elapsed >= TL)
            break;

        int resetPlane = (int)(rng() % K);
        if(iter % 3 == 0) {
            resetPlane = 0;
            for(int p = 1; p < K; ++p) {
                if(currentLegCount[p] < currentLegCount[resetPlane])
                    resetPlane = p;
            }
        }

        vector<vector<Flight>> candPlaneFlights = currentPlaneFlights;
        vector<int> candHeadCity = currentHeadCity;
        vector<int> candHeadTime = currentHeadTime;
        vector<int> candLegCount = currentLegCount;

        auto order = makeSeedOrder(iter + 1);
        int seed = order[(resetPlane * 7 + iter) % N];
        candPlaneFlights[resetPlane].clear();
        candHeadCity[resetPlane] = seed;
        candHeadTime[resetPlane] = MAX_SLOT;
        candLegCount[resetPlane] = 0;

        auto candLatestAll = baseLatestAll;
        for(int p = 0; p < K; ++p) {
            for(const auto &f : candPlaneFlights[p])
                applyFlightToLatestAll(candLatestAll, f.a, f.b, f.s, f.t);
        }
        long double candCi = calcCiFromLatest(candLatestAll);
        double candScore = (totalDen > 0.0L ? (double)(candCi / totalDen) : 0.0);

        extendGreedy(
            candPlaneFlights, candHeadCity, candHeadTime, candLegCount, candLatestAll, candCi, candScore, resetPlane);

        bool accept = (candScore >= currentScore);
        if(!accept) {
            long double delta = currentScore - candScore;
            long double temp = 0.0005L;
            long double prob = expl(-delta / temp);
            long double r = (long double)(rng() & ((1ULL << 53) - 1)) / (long double)(1ULL << 53);
            if(r < prob)
                accept = true;
        }
        if(accept) {
            currentPlaneFlights.swap(candPlaneFlights);
            currentHeadCity.swap(candHeadCity);
            currentHeadTime.swap(candHeadTime);
            currentLegCount.swap(candLegCount);
            latestAll.swap(candLatestAll);
            currentCi = candCi;
            currentScore = candScore;
        }

        if(candScore > bestScoreAll) {
            auto candFlights = flattenPlaneFlights(candPlaneFlights);
            double exact = evaluator.score(candFlights, demands);
            if(exact > bestScoreAll) {
                bestScoreAll = exact;
                bestTrial = iter;
                bestPlaneFlights = candPlaneFlights;
            }
        }

        if(iter % 50 == 0) {
            int curFlightCnt = 0;
            for(const auto &v : currentPlaneFlights)
                curFlightCnt += (int)v.size();
            cerr << fixed << setprecision(12)
                 << "iter=" << iter
                 << " current=" << currentScore
                 << " best=" << bestScoreAll
                 << " flights=" << curFlightCnt << '\n';
        }
        iter++;
    }

    auto scorePlaneFlights = [&](const vector<vector<Flight>> &pf) {
        return evaluator.score(flattenPlaneFlights(pf), demands);
    };

    vector<vector<Flight>> planeFlights = bestPlaneFlights;
    double finalScore = bestScoreAll;
    for(int p = 0; p < K; ++p) {
        auto &pf = planeFlights[p];
        if(pf.empty())
            continue;
        int minStart = pf.front().s;
        int maxEnd = pf.back().t;
        int lo = max(-6, -minStart);
        int hi = min(6, MAX_SLOT - maxEnd);
        int bestDelta = 0;
        double bestLocal = finalScore;
        for(int delta = lo; delta <= hi; ++delta) {
            if(delta == 0)
                continue;
            for(auto &f : pf) {
                f.s += delta;
                f.t += delta;
            }
            double s = scorePlaneFlights(planeFlights);
            for(auto &f : pf) {
                f.s -= delta;
                f.t -= delta;
            }
            if(s > bestLocal) {
                bestLocal = s;
                bestDelta = delta;
            }
        }
        if(bestDelta != 0) {
            for(auto &f : pf) {
                f.s += bestDelta;
                f.t += bestDelta;
            }
            finalScore = bestLocal;
        }
    }
    vector<Flight> finalFlights = flattenPlaneFlights(planeFlights);

    vector<int> flownCity(N, 0);
    for(const auto &f : finalFlights) {
        flownCity[f.a] = 1;
        flownCity[f.b] = 1;
    }

    for(int i = 0; i < K; ++i) {
        cout << planeFlights[i].size() << '\n';
        for(const auto &f : planeFlights[i]) {
            cout << (f.a + 1) << ' ' << slotToTime(f.s) << ' ' << (f.b + 1) << ' ' << slotToTime(f.t) << '\n';
        }
    }

    cerr << fixed << setprecision(12)
         << "best_trial=" << bestTrial << ' '
         << "score=" << finalScore
         << " unique_cities=" << count(flownCity.begin(), flownCity.end(), 1)
         << " flights=" << finalFlights.size() << '\n';

    return 0;
}