{"problem":{"name":"H. Win Strategy","description":{"content":"You are at a programming contest where there will be $n$ problems. For each problem you know at what time it will be available for you to read (and solve). Also you know how much time you need to solv","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10196H"},"statements":[{"statement_type":"Markdown","content":"You are at a programming contest where there will be $n$ problems. For each problem you know at what time it will be available for you to read (and solve). Also you know how much time you need to solve it.\n\nTo solve a problem, you need to spend the needed time continuously without switching between different problems.\n\nFind the maximum number of problems you can solve in the given contest time.\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 250$), the number of test cases.\n\nThe first line of each test case contains two space-separated integers $n$ and $L$ ($1 <= n, L <= 1000$), the number of problems and the length of the contest, respectively.\n\nEach of the following $n$ lines contains two space-separated integers $a_i$ and $b_i$ ($1 <= a_i, b_i <= L$), which means the $i^(t h)$ problem will be available at minute $a_i$ and you need $b_i$ minutes to solve it.\n\nProblems will be given in a non-decreasing order of $a_i$.\n\nFor each test case, output a single line with the maximum number of problems you can solve during the contest.\n\n## Input\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 250$), the number of test cases.The first line of each test case contains two space-separated integers $n$ and $L$ ($1 <= n, L <= 1000$), the number of problems and the length of the contest, respectively.Each of the following $n$ lines contains two space-separated integers $a_i$ and $b_i$ ($1 <= a_i, b_i <= L$), which means the $i^(t h)$ problem will be available at minute $a_i$ and you need $b_i$ minutes to solve it.Problems will be given in a non-decreasing order of $a_i$.\n\n## Output\n\nFor each test case, output a single line with the maximum number of problems you can solve during the contest.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of problems.  \n- Let $ L_k \\in \\mathbb{Z} $ be the contest length.  \n- Let $ P_k = \\{(a_{k,i}, b_{k,i}) \\mid i \\in \\{1, \\dots, n_k\\}\\} $ be the set of problems, where $ a_{k,i} $ is the availability time and $ b_{k,i} $ is the solving time for problem $ i $, with $ a_{k,1} \\leq a_{k,2} \\leq \\dots \\leq a_{k,n_k} $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 250 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\leq n_k \\leq 1000 $  \n   - $ 1 \\leq L_k \\leq 1000 $  \n   - $ 1 \\leq a_{k,i}, b_{k,i} \\leq L_k $ for all $ i \\in \\{1, \\dots, n_k\\} $  \n   - $ a_{k,i} \\leq a_{k,i+1} $ for all $ i \\in \\{1, \\dots, n_k-1\\} $\n\n**Objective**  \nFor each test case $ k $, find the maximum number of problems that can be solved such that:  \n- Each problem $ i $ is solved continuously for $ b_{k,i} $ minutes.  \n- Problem $ i $ is started at time $ \\geq a_{k,i} $.  \n- The entire solving schedule finishes by time $ L_k $.  \n- Problems are scheduled in an order consistent with their availability (non-decreasing $ a_i $), and no overlapping or switching between problems.  \n\nLet $ S_k \\subseteq \\{1, \\dots, n_k\\} $ be the selected subset of problems.  \nMaximize $ |S_k| $ subject to the existence of start times $ s_i \\geq a_{k,i} $ for $ i \\in S_k $, with $ s_i + b_{k,i} \\leq s_j $ for consecutive selected problems $ i, j \\in S_k $ (in order of increasing $ a_i $), and $ s_{\\min} + b_{\\min} \\leq L_k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10196H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}