C - Aerotaxi - 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;


public class AeroTaxi_2_er {

    public static void main(String[] args) throws IOException {
        Flying2 flying = new Flying2();
        flying.solve();
        flying.print();
    }
}

class Flying2 {

    class Segment {

        Segment(int left, int right, int sl, int cl){
            this.left = left;
            this.right = right;
            downPoint = left+1;
            startLevel = sl;
            currentLevel = cl;
            points = new int[n];
        }

        Segment(int left, int right, int downPoint, int sl, int cl){
            this.left = left;
            this.right = right;
            this.downPoint = downPoint;
            startLevel = sl;
            currentLevel = cl;
            points = new int[n];
        }

        Segment(Segment s) {
            this.left = s.left;
            this.right = s.right;
            this.downPoint = s.downPoint;
            startLevel = s.startLevel;
            currentLevel = s.currentLevel;
            points = new int[n];
            for (int i = 0; i < currentLevel; i++){
                points[i] = s.points[i];
            }
        }

        void upgrade(int dp, int r){
            downPoint = dp+1;
            points[currentLevel] = dp;
            currentLevel++;
            right = r;
        }

        public String toString() {
            return "[" + left + ", " + right + "] (" + downPoint + ") (" + startLevel + " -> " + currentLevel + ")";
        }

        int left;
        int right;
        int downPoint;
        int startLevel;
        int currentLevel;
        int[] points;
    }


    Flying2() throws IOException {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        n = nextInt();
        t = nextInt();

        free = new ArrayList<ArrayList<Segment>>(n);
        for (int i = 0; i < n; i++){
            free.add(new ArrayList<Segment>());
        }

        freeSize = new int[n];

        int c;
        int lb;
        int rb;
        int s;
        int f;

        for (int i = 0; i < n; i++){
            c = nextInt();

            lb = 0;

            for (int j = 0; j < c; j++){
                s = nextInt();
                f = nextInt();

                if (lb == s) {
                    lb = f;
                }
                else {
                    rb = s;
                    free.get(i).add(new Segment(lb, rb, i, i));
                    lb = f;
                    freeSize[i]++;
                }
            }

            rb = ALWAYS;
            free.get(i).add(new Segment(lb, rb, i, i));
            freeSize[i]++;

        }

        union = new ArrayList<Segment>();
        newUnion = new ArrayList<Segment>();
        answer = new Segment(ALWAYS, ALWAYS, 0, 0);
    }

    int nextInt() throws IOException {
        in.nextToken();
        return (int)in.nval;
    }


    boolean check(Segment s){
        if ((s.right - s.left) >= t){
            if (s.left < answer.left) {
                answer = s;
            }
            return true;
        }
        return false;
    }

    void phase(int startEchelon){
        union.clear();
        newUnion.clear();

        int szu = 0;
        for (Segment s: free.get(startEchelon)){
            if (check(s)) {
                break;
            }
            union.add(new Segment(s));
            szu++;
        }

        int sznu = 0;

        for (int i = startEchelon + 1; i < n; i++){

            if (szu == 0) {
                break;
            }

            int iu = 0;
            int ie = 0;

            while ((iu < szu) && (ie < freeSize[i])) {

                Segment cs = free.get(i).get(ie);
                Segment us = union.get(iu);

                if (answer.left <= us.left) {
                    break;
                }

                if (cs.right <= us.downPoint) {
                    ie++;
                }
                else if (cs.left <= us.left) {
                    ie++;
                }
                else if (us.right < cs.left) {
                    iu++;
                }
                else if (cs.left < us.downPoint) {
                    Segment ns = new Segment(us);
                    ns.upgrade(us.downPoint, cs.right);
                    if (check(ns)) {
                        break;
                    }
                    newUnion.add(ns);
                    sznu++;
                                        ie++;
                }
                else if (us.downPoint <= cs.left) {
                    Segment ns = new Segment(us);
                    ns.upgrade(cs.left, cs.right);
                    if (check(ns)) {
                        break;
                    }

                    newUnion.add(ns);
                    sznu++;
                    ie++;
                }

             }

            ArrayList<Segment> tmp = union;
            union = newUnion;
            newUnion = tmp;
            szu = sznu;
            newUnion.clear();
            sznu = 0;

        }

    }

    void solve() {
        for (int i = 0; i < n; i++){
            phase(i);
        }
    }

    void print() {
        System.out.println(answer.left);

        int h = answer.startLevel + 1;
        int d = answer.currentLevel - answer.startLevel;
        System.out.print(h);
        System.out.print(" ");
        System.out.println(d);

        boolean first = true;
        for (int i = answer.startLevel; i < answer.currentLevel; i++){
            if (first) {
                first = false;
            }
            else {
                System.out.print(" ");
            }
            System.out.print(answer.points[i]);
        }

        System.out.println();
    }


    Segment answer;

    ArrayList<Segment> union;
    ArrayList<Segment> newUnion;

    ArrayList<ArrayList<Segment>> free;
    int[] freeSize;

    StreamTokenizer in;

    int n;
    int t;

    static final int ALWAYS = 1000*1000*1000 + 100*1000;
}