{"problem":{"name":"C. Aerotaxi","description":{"content":"Dragon poured Princess another cup of tea. Princess sighed faintly and asked: — Do princesses and princes in neighbouring castles have rental agreements too? — Yes, of course! — Dragon answered, — T","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10070C"},"statements":[{"statement_type":"Markdown","content":"Dragon poured Princess another cup of tea. Princess sighed faintly and asked:\n\n— Do princesses and princes in neighbouring castles have rental agreements too?\n\n— Yes, of course! — Dragon answered, — To tell the truth, princesses are troublesome. So, every progressive dragon would rather lease his castles to a prince. However, the demand for rent of castles is so small now, many dragons have side job as taxi. As aerotaxi, I mean.\n\nAs Dragon told, the inhabitants of castles fly on dragons on business quite often. While flying they do not like to cross each other and require no one of their neighbours could see them. And a dispatcher, who schedules flights, has a hard work because of that.\n\nLet us describe a simplified model of flights. Suppose air space is divided into n \"air corridors\". These air corridors are indexed, each corridor locates in certain height; the smaller the number of a corridor, the higher the corridor is. \n\nDragon begins his flight taking up any vacant corridor. During the flight, a dragon may descend and he does it step by step. The dispatcher demands dragons to descend only in integer moments of time and by only one corridor down. So, if a dragon flies along the jth air corridor, he can descend down to (j + 1)th air corridor (if (j + 1)th corridor exists). If a dragon occupies some air corridor, he must fly along it for at least one time unit. \n\nDragon moves at a constant horizontal speed during the whole flight. Time for moving between air corridors is negligible and should be considered zero. Dragon can't stop during the flight.\n\nDispatcher has a schedule wherein the periods of corridors' occupation are specified. Each period consists of some intervals of form (s, f) (s < f); it is believed that a dragon can occupy air corridor at interval's boundaries s and f, but not in any time strictly between s and f.\n\nDispatcher gets a request for a flight t time units long from another dragon, and he is to allocate some air corridors for the flight. Dragon's passenger wants to arrive at a destination as soon as possible.\n\nYour task is to compute the time of flight's beginning and the times in which the dragon should descend (if it is necessary). \n\nThe first line contains integers n and t (1 ≤ n ≤ 100,  1 ≤ t ≤ 10000) — the number of air corridors and flight time.\n\nEach of next n lines contain an air corridor's occupation periods. The line starts with integer cj (0 ≤ cj ≤ 100) — the number of time intervals. After it all the intervals are listed. An interval consists of two space-separated integers s(j)k и f(j)k (k = 1, 2, ..., cj). It is guaranteed that 0 ≤ s(j)1 < f(j)1 < s(j)2 < ... < f(j)cj ≤ 109.\n\nDragon (who requests a flight) is ready to begin his flight at any time starting from 0.\n\nIn the first line print an integer a — the earliest time a flight can start. \n\nIn the second line print two integers h and d — the number of air corridor where the flight starts and the number of descends.\n\nIn the third line print d space-separated integers — the times (in chronological order) in which the dragon should descend.\n\nIf there are more than one answer, choose any of them.\n\nLet us explain the samples.\n\nIn the first sample dragon may start the flight at time 4 and occupy air corridor #1. At time 10 he descends to the 2nd air corridor. Flight ends at time 12.\n\nIn the second sample dragon may begin flight at time 0 and occupy the 3rd air corridor. At time 3 he descends to the air corridor number 4, at time 5 he descends again — to air corridor number 5.\n\nIn the third sample the earliest time of flight start is 8. Indeed, dragon can descend from the first air corridor to the second air corridor at time 4, then he stays in the second air corridor until time 5. At time 5 he descends to the 3rd air corridor, but he cannot stay in this corridor after time 5. At time 8 dragon may begin his flight in the 2nd or in the 3rd air corridor and move in the corridor until the end of the flight.\n\n## Input\n\nThe first line contains integers n and t (1 ≤ n ≤ 100,  1 ≤ t ≤ 10000) — the number of air corridors and flight time.Each of next n lines contain an air corridor's occupation periods. The line starts with integer cj (0 ≤ cj ≤ 100) — the number of time intervals. After it all the intervals are listed. An interval consists of two space-separated integers s(j)k и f(j)k (k = 1, 2, ..., cj). It is guaranteed that 0 ≤ s(j)1 < f(j)1 < s(j)2 < ... < f(j)cj ≤ 109.Dragon (who requests a flight) is ready to begin his flight at any time starting from 0.\n\n## Output\n\nIn the first line print an integer a — the earliest time a flight can start. In the second line print two integers h and d — the number of air corridor where the flight starts and the number of descends.In the third line print d space-separated integers — the times (in chronological order) in which the dragon should descend.If there are more than one answer, choose any of them.\n\n[samples]\n\n## Note\n\nLet us explain the samples.In the first sample dragon may start the flight at time 4 and occupy air corridor #1. At time 10 he descends to the 2nd air corridor. Flight ends at time 12.In the second sample dragon may begin flight at time 0 and occupy the 3rd air corridor. At time 3 he descends to the air corridor number 4, at time 5 he descends again — to air corridor number 5.In the third sample the earliest time of flight start is 8. Indeed, dragon can descend from the first air corridor to the second air corridor at time 4, then he stays in the second air corridor until time 5. At time 5 he descends to the 3rd air corridor, but he cannot stay in this corridor after time 5. At time 8 dragon may begin his flight in the 2nd or in the 3rd air corridor and move in the corridor until the end of the flight.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of air corridors (indexed $ 1 $ to $ n $, where lower index = higher altitude).  \nLet $ t \\in \\mathbb{Z}^+ $ be the required flight duration.  \nFor each corridor $ j \\in \\{1, \\dots, n\\} $, let $ I_j = \\bigcup_{k=1}^{c_j} [s_{j,k}, f_{j,k}] $ be the set of occupied time intervals, with $ 0 \\leq s_{j,1} < f_{j,1} < s_{j,2} < \\dots < f_{j,c_j} \\leq 10^9 $, and $ c_j \\in \\mathbb{Z}_{\\geq 0} $.  \nThe complement $ \\overline{I_j} = [0, \\infty) \\setminus I_j $ represents available time intervals in corridor $ j $.  \n\n**Constraints**  \n1. A flight begins at some time $ a \\geq 0 $.  \n2. The flight lasts exactly $ t $ time units: ends at $ a + t $.  \n3. The dragon starts in some corridor $ h \\in \\{1, \\dots, n\\} $, and may descend at integer times to corridor $ j+1 $ from corridor $ j $ (only downward, one level at a time).  \n4. At all times during the flight, the dragon must be in a corridor $ j $ during an available interval $ \\overline{I_j} $.  \n5. The dragon must occupy each corridor for at least one full time unit.  \n6. Descents occur only at integer times and are instantaneous.  \n7. Horizontal movement is constant; no stopping.  \n\n**Objective**  \nFind the earliest start time $ a \\in \\mathbb{R}_{\\geq 0} $, initial corridor $ h \\in \\{1, \\dots, n\\} $, number of descents $ d \\in \\mathbb{Z}_{\\geq 0} $, and descent times $ \\tau_1, \\dots, \\tau_d \\in \\mathbb{Z} $ such that:  \n- $ a \\in \\overline{I_h} $,  \n- $ a + t \\in \\overline{I_{h+d}} $,  \n- For each $ i \\in \\{0, \\dots, d\\} $, the interval $ [\\tau_i, \\tau_{i+1}] \\subseteq \\overline{I_{h+i}} $, where $ \\tau_0 = a $, $ \\tau_{d+1} = a + t $, and $ \\tau_1 < \\dots < \\tau_d $ are descent times (with $ \\tau_i \\in \\mathbb{Z} $),  \n- Each segment $ [\\tau_i, \\tau_{i+1}] $ has length $ \\geq 1 $,  \n- $ \\tau_i \\in \\overline{I_{h+i}} \\cap \\overline{I_{h+i+1}} $ for all $ i \\in \\{1, \\dots, d\\} $.  \n\nOutput $ a $, $ h $, $ d $, and $ \\tau_1, \\dots, \\tau_d $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10070C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}