{"raw_statement":[{"iden":"statement","content":"#cf_span(class=[tex-font-style-underline], body=[\"This should definitely look much better...\"]) – said the fire brigade captain Peetle-Son. He got used to it that his decisions concerning the management of the Compulsory Beetle Fire Brigade units have always been optimal. Unfortunately, the reports were exceptionally alarming – the fire was spreading fast. Soon it turned out that the cause of the fire was not the experiment conducted by professor Beetlestein, but a well-planned sabotage action carried out by the Fighters for Going Back to the Future.\n\nCourageous firemen under the command of captain Peetle-Son are now threatened not only by a direct fight with the element. Additionally they must pay attention to the explosive charges placed by the saboteurs, which effectively enlarge the disaster area and directly threaten the life of the rescuers. Even the most cautious captain could not predict such a scenario. Hospitals (very rare in this part of the Universum) are bursting at the seams and are unable to take in the heroes fighting with the fire and explosions. The best doctors and professors of the beetle surgery do their best in order to save the life of each fireman.\n\nIn the hospital, there are specialized surgery tables used to carry out medical treatments. Each table is of a specific type defining the kinds of treatment which are to be performed on them. Each kind of a treatment may be carried out on various (known in advance) types of surgery tables. Each type of the table may be used for more than one kind of the treatment.\n\n*Example*. The treatment of \"leg amputation\" may be carried out both on a table equipped with a \"laser blade\" (table of the first type) and a table equipped with (ouch!) \"sword blade\" (table of another type). Next: a table equipped with a \"laser blade\" may be for example used in the \"leg amputation\" (_x_ type treatment), in \"resection of dead tissues\" (_y_ type of treatment) and in \"eyesight correction\" (_z_ type treatment).\n\nN brave beetlejumpers should be provided with medical aid. Treatment of each of them is individually adjusted to the current patient's condition. The entire recovery process of an i-th beetlejumper is composed of mi kinds of treatments (, where  is the number of all kinds of treatment known to the beetle surgeons) which must be carried out in an ordered sequence. Each j-th treatment can be carried out by a qualified doctor in time tj on one out of the Rj table types. If the surgical table is not occupied at the moment, the treatment may begin immediately.\n\n*Example*. If the patient is to undergo three treatments: (1) \"general anesthesia administration\", (2) \"leg amputation\" and (3) \"permanent prosthesis attachment\", each of the treatments may be performed when a particular operating table is unoccupied #cf_span(class=[tex-font-style-underline], body=[and]) when patient's previous treatments are finished. It means that (2) \"leg amputation\" can be performed only after finishing (1) \"general anesthesia administration\", and (3) \"permanent prosthesis attachment\" can be performed only after (2) \"leg amputation\".\n\nDoctors must act quickly and decidedly – each minute may save a life of a beetlejumper! Fortunately, the hospital staff may use more than one table of each type, what enables parallel strenuous work of the doctors. However, the costs of drawing on the reserves of such equipment are significant...\n\nYour task is to help the hospital staff to plan the treatment process of the beetlejumpers. Unusual threat in the fire area causes great losses among the fire brigades thus it is important to perform the surgeries as quickly as possible and to effectively use the surgical tables.\n\nThe first line of a test set includes one natural number M which is the number of the types of surgery tables. The second line includes M (separated by single whitespace characters) natural numbers Lk which are the numbers of surgery tables of each type actually available in the hospital.\n\nEach surgery table has its own identifier (ID) which is a subsequent integer number. For example, if M = 2, L1 = 3 and L2 = 2, then the subsequent surgery tables are marked with identifiers ID={1, 2, 3, 4, 5}, where the tables with the ID={1, 2, 3} are the tables of the first type and the tables of the ID={4, 5} of the second type.\n\nThe third line of a test set consists of one natural number , which is the number of the kinds of treatments known to the beetle surgeons. Each j-th line from subsequent  lines is composed of (2 + Rj) natural lines meaning respectively: identifier of j-th kind of a treatment, its time (tj) and identifiers of the types of surgery tables on which it may be performed.\n\nThe next line includes one natural number N which stands for the number of the injured beetlejumpers. Each i-th line of the subsequent N lines is composed of (1 + mi) natural numbers meaning respectively: identifier of a treated beetlejumper and identifier of the subsequent kinds of treatments necessary to be carried out in order to cure i-th patient.\n\n1 ≤ N ≤ 103\n\n1 ≤ M, Lk ≤ 5·103\n\n1 ≤ Rj ≤ M\n\n\n\n1 ≤ tj ≤ 104\n\nOutput data should in the first line consist of two natural numbers separated by a whitespace: S denoting the number of used surgery tables and T denoting the time necessary for curing all beetlejumpers (from the beginning of the first treatment till the end of the last one).\n\nEach of the subsequent S lines describes one surgery table. For each surgery table, its ID and subsequent treatments carried out on it should be given. Each treatment performed on a given table is defined by a pair of natural numbers: identifier of a beetlejumper related to this treatment and a treatment sequential number from the patient's treatments list (starting from 1). Surgery tables should be described in an ascending order (in respect of their identifiers). The numbers within the lines should be separated by single whitespace characters.\n\nIf the following conditions are fulfilled: \n\nFor the input data (this example is not from the official testset, it is just example): \n\nA possible correct answer is: \n\n\n\n"},{"iden":"input","content":"The first line of a test set includes one natural number M which is the number of the types of surgery tables. The second line includes M (separated by single whitespace characters) natural numbers Lk which are the numbers of surgery tables of each type actually available in the hospital.Each surgery table has its own identifier (ID) which is a subsequent integer number. For example, if M = 2, L1 = 3 and L2 = 2, then the subsequent surgery tables are marked with identifiers ID={1, 2, 3, 4, 5}, where the tables with the ID={1, 2, 3} are the tables of the first type and the tables of the ID={4, 5} of the second type.The third line of a test set consists of one natural number , which is the number of the kinds of treatments known to the beetle surgeons. Each j-th line from subsequent  lines is composed of (2 + Rj) natural lines meaning respectively: identifier of j-th kind of a treatment, its time (tj) and identifiers of the types of surgery tables on which it may be performed.The next line includes one natural number N which stands for the number of the injured beetlejumpers. Each i-th line of the subsequent N lines is composed of (1 + mi) natural numbers meaning respectively: identifier of a treated beetlejumper and identifier of the subsequent kinds of treatments necessary to be carried out in order to cure i-th patient.1 ≤ N ≤ 1031 ≤ M, Lk ≤ 5·1031 ≤ Rj ≤ M1 ≤ tj ≤ 104"},{"iden":"output","content":"Output data should in the first line consist of two natural numbers separated by a whitespace: S denoting the number of used surgery tables and T denoting the time necessary for curing all beetlejumpers (from the beginning of the first treatment till the end of the last one).Each of the subsequent S lines describes one surgery table. For each surgery table, its ID and subsequent treatments carried out on it should be given. Each treatment performed on a given table is defined by a pair of natural numbers: identifier of a beetlejumper related to this treatment and a treatment sequential number from the patient's treatments list (starting from 1). Surgery tables should be described in an ascending order (in respect of their identifiers). The numbers within the lines should be separated by single whitespace characters."},{"iden":"scoring","content":"If the following conditions are fulfilled:   output data are in the correct format,  a proper schedule of treatments may be established taking into consideration their sequence for each patient,  all treatments for each of the listed beetlejumpers were planned,  all treatments are properly assigned to the surgery tables,  the number of surgery tables (S) is not higher than  , i.e. the number of all available tables,  time necessary for the recovery of all beetlejumpers (T) was properly calculated,  then the score for a given set is equal to the value  (rounded off to three decimal places), where the value T0 is the total time of all treatments of all beetlejumpers (irrespective of the availability of the tables) and Pbly is the sum of maximum P values achieved by last year's contestants for all test sets. Otherwise the score is 0."},{"iden":"note","content":"For the input data (this example is not from the official testset, it is just example): 41 1 1 241 5 1 22 10 13 15 1 2 3 44 3 331 1 2 3 42 3 13 1 2 1 1A possible correct answer is: 4 351 1 1 1 2 3 2 3 3 3 42 3 1 2 23 2 1 1 45 1 3  The use of 4 surgery tables (S = 4) was planned for the recovery of all beetlejumpers.  From the beginning of the first treatment till the end of the last treatment the time equals T = 35.  The total number of available tables is 5, L = 1 + 1 + 1 + 2.  Time of treatments of particular beetlejumpers:   Beetlejumper with the ID = 1: 5 + 10 + 15 + 3 = 33,  Beetlejumper with the ID = 2: 15 + 5 = 20,  Beetlejumper with the ID = 3: 5 + 10 + 5 + 5 = 25.   The total time of all treatments T0 = 33 + 20 + 25 = 78.  Score for the answer equals , after rounding the P value equals to 0.018. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of galaxies.  \nFor each galaxy $ i \\in \\{1, \\dots, n\\} $, let $ [a_i, b_i) $ be a half-open time interval where $ a_i, b_i \\in \\mathbb{Z} $, $ 0 \\leq a_i < b_i \\leq 24 $, representing the availability window from the start of hour $ a_i $ to the start of hour $ b_i $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. For each $ i \\in \\{1, \\dots, n\\} $: $ 0 \\leq a_i < b_i \\leq 24 $\n\n**Objective**  \nFind the maximum number of overlapping intervals $ [a_i, b_i) $ that cover any single integer hour $ h \\in \\{0, 1, \\dots, 23\\} $.  \nThat is, compute:  \n$$\n\\max_{h \\in \\{0, 1, \\dots, 23\\}} \\left| \\left\\{ i \\in \\{1, \\dots, n\\} \\mid a_i \\leq h < b_i \\right\\} \\right|\n$$","simple_statement":"Find the maximum number of galaxies available at the same one-hour time slot.","has_page_source":false}