【正文】 s to make a plan to maximize the total number of berthed ships, in other words, minimize the number of unberthed ships. Just like other packing problems, it is difficult for Max to solve. But he believes that the best team of the contest is able to solve it both correctly and effectively. Do your guys want to be the best? Just try it. Input: Input contains many test sets. A test data set is defined as follow: The first line of test data set is two integers: m and n, separated by one or more spaces(1≤ m≤ 10, 1≤ n≤ 100000). m is the number of sections in the port, and n is the number of ships. The next m lines, one positive integer r (that means the length of the section is r hundred meters long) per line. The length of each section does not exceed 10000 hundred meters. The next n lines gives one ship information on each line, with three nonnegative integers s, e, sec (0≤ s≤ e,1≤ sec≤ m) per line, s is the arrival time of the ship, e is the departure time of the ship, and sec is the section which the ship should be berthed in. Input is ended by EOF. You can assume that all the input data are legal. Output: For each test data set you should output one integer, the maximal number of the berthed ships, per line. Sample Input: 2 6 3 3 1 2 1 1 2 1 32 1 2 1 1 2 1 1 2 2 1 2 2 1 3 2 1 3 1 2 6 1 2 8 1 1 4 2 1 3 1 5 6 1 2 8 1 4 10 1 Sample Output: 5 2 3 （ 例題 2） CTSC 2022 DAY2 pendant 掛綴 【問題描述】 “珠綴花蕊，人間幾多酸淚”?? 掛綴在很早就被人們作為一種裝飾品，垂墜的風韻，華麗搖曳的擺動，展現(xiàn)出一種與眾不同的優(yōu)雅與高貴。而我們的主人公小 Q，正想買一條漂亮的掛綴放 33 在寢室里作為裝飾。 掛墜的構成，是由若干粒綴珠相互連接而成。每一個綴珠由三部分組成：分別是珠子、珠子上方的連接環(huán)與珠子下方的掛鉤（如下圖）。我們可以簡單的認為從上往下數(shù)的第 i 個綴珠是將它的連接環(huán)套在其上方（也就是第 i1 個）綴珠的掛鉤之上（第一個除外）。小 Q 想買一根足夠 長的掛綴，這樣顯得更有韻味 ? 然而商店的老板告訴小 Q，掛綴是不可能做到任意長的，因為每一個珠子都受到重力作用，對其上方的掛鉤有一定的拉力，而掛鉤的承受能力是有限的。老板還告訴小 Q，他一共擁有 N 個珠綴（假設每一個珠綴都很漂亮，小 Q 都很喜歡），每個珠綴都有其各自的重量與承受能力。一個掛綴是穩(wěn)定的，當且僅當對于其上的每一個珠綴，它下方所有珠綴的重量和（不包含自身）不超過其掛鉤的承受能力。 小 Q 希望她的掛綴盡量長，你能幫她計算出最長可能的穩(wěn)定掛綴么？當然，如果有多個可選解，小 Q 希望總重量最小的。 【輸 入文件】 輸入文件 第一行包含一個正整數(shù) N，表示商店擁有的珠綴數(shù)目。 接下來 N 行，每行兩個整數(shù) (Ci , Wi)，分別表示第 i 個珠綴的承受能力與重量。 【輸出文件】 輸出文件 包行兩行。第一行包含一個整數(shù) L，表示可以找到的最長穩(wěn)定掛綴長度。第二行包含一個整數(shù) W，表示可以找到的長度為 L 的穩(wěn)定掛綴中的最小重量和。 【樣例輸入】 4 3 5 5 1 3 2 4 6 【樣例輸出】 34 3 8 【評分標準】 每一個測試點單獨評分，對于每一個測試點： 如果掛綴長度 L 與答案一 致，且最小重量和 W 也正確，則得 10 分。 如果掛綴長度 L 與答案一致，而最小重量和 W 與答案不一致，該測試點則得4 分。 否則得 0 分。 【數(shù)據(jù)規(guī)?！? 對于 30%的數(shù)據(jù)， N ≤ 10000； 對于 100%的數(shù)據(jù)， N ≤ 202200； 對于所有的數(shù)據(jù)， Wi, Ci 不超過 231。 （ 例題 ） Europe Southeastern 2022 Problem D Loan Scheduling The North Pole Beach Bank has to decide upon a set App of mortgage applications. Each application a ∈ App has an acceptance deadline da , ie. the required loan must be paid at a time ta , 0≤ ta≤ da . If the application is accepted the Bank gets a profit pa . Time is measured in integral units starting from the conventional time origin 0, when the Bank decides upon all the App applications. Moreover, the Bank can pay a maximum number of L loans at any given time. The Bank policy if focussed solely on profit: it accepts a subset S ∈ App of applications that maximizes the profit ? ? ??? Sa apSprof it. The problem is to pute the maximum profit the Bank can get from the given set App of mortgage applications. For example, consider that L = 1 , App = {a, b, c, d} , (pa, da) = (4, 2) , (pb, db) = (1, 0) , (pc, dc) = (2, 0) , and (pd, dd) = (3, 1) . The table below shows all possible sets of accepted mortgage applications and the 35 scheduling of the loan payments. The highest profit is 9 and corresponds to the set {c, d, a} . The loan requested by the application c is paid at time 0, the loan corresponding to d is paid at time 1, and, finally, the loan of a is paid at time 2. Time Sets of accepted applications and loan scheduling 0 a b c d b c b B c c d d a b c 1 a d d d a a a d d d d 2 a A a a a a a Profit 4 4 4 1 2 3 3 4 5 5 5 6 6 7 7 7 7 8 9 Write a program that reads sets of data from the standard input. Input Each data set corresponds to a set of mortgage applications and starts with two integers: 0≤ N≤ 10000 that shows the number of applications in the set, and 0≤ L≤ 100 which shows the maximum number of loans the Bank can pay at any given time. Follow N pairs of integers pi di , i = 1, N , that specify the profit 0≤ pi≤ 10000 and the deadline 0≤ di≤ 10000 of the application i. Input data are separated by white spaces, are correct, and terminate with an end of file. Output For each data set the program putes the maximum profit the Bank can get from the accepted mortgage applications corresponding to that data set. The result is printed on standard output from the beginning of a line. There must be no empty lines on output. An example of input/output is shown below. Sample Input 4 1 4 2 1 0 2 0 3 1 36 7 2 200 1 200 1 100 0 1000 2 80 1 50 20 500 1 0 100 1 0 4 1000 Sample Output 9 20 50 0 0 (例題 ) ACM/ICPC Regional Warmup Contest 2022 Problem E n sprinklers are installed in a horizontal strip of grass l meters long and w meters wide. Each sprinkler is installed at the horizontal center line of the strip. For each sprinkler we are given its position as the distance from the left end of the center line and its radius of operation. What is the minimum number of sprinklers to turn on in order to water 37 the entire strip of grass? Input Input consists of a number of cases. The first line for each case contains integer numbers n, l and w with n = 10000. The next n lines contain two integers giving the position of a sprinkler and its radius of operation. (The picture above illustrates the first case from the sample input.) Output For each test case output the minimum number of sprinkler