{"problem":{"name":"I. Ice-cream Knapsack","description":{"content":"There is a wonderful ice-cream shop that contains $N$ ice-creams, such that each ice-cream is represented by two numbers $C_i$ and $H_i$ denoting the number of calories and the happiness value, respec","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10199I"},"statements":[{"statement_type":"Markdown","content":"There is a wonderful ice-cream shop that contains $N$ ice-creams, such that each ice-cream is represented by two numbers $C_i$ and $H_i$ denoting the number of calories and the happiness value, respectively. \n\nYou want to buy exactly $K$ ice-creams such that the calories of the densest ice-cream (the one with most calories) are as minimal as possible. If there is more than one way to do that, you want to maximize the total happiness of the ice-creams you will buy, that is the sum of the happiness values of the chosen ice-creams.\n\nThe first line of the input contains a single integer $T$ specifying the number of test cases.\n\nEach test case begins with a line containing two integers $N$ and $K$ ($1 <= K <= N <= 10^5$), in which $N$ is the number of ice-creams in the shop, and $K$ is the number of ice-creams you want to buy. \n\nThen a line follows containing $N$ integers $C_1, \\\\\\\\cdots, C_N$ ($0 <= C_i <= 10^9$), in which $C_i$ is the number of calories in the $i^(t h)$ ice-cream. Then a line follows containing $N$ integers $H_1, \\\\\\\\cdots, H_N$ ($0 <= H_i <= 10^9$), in which $H_i$ is the happiness value of the $i^(t h)$ ice-cream.\n\nFor each test case, print a single line containing two space-separated integers representing the calories of the densest ice-cream you will buy and the total happiness of the ice-creams you will buy, respectively.\n\nRemember that your goal is to buy $K$ ice-creams such that the calories of the densest ice-cream (the one with most calories) are as minimal as possible. If there is more than one way to do that, you want to maximize the total happiness of the ice-creams you will buy.\n\n## Input\n\nThe first line of the input contains a single integer $T$ specifying the number of test cases.Each test case begins with a line containing two integers $N$ and $K$ ($1 <= K <= N <= 10^5$), in which $N$ is the number of ice-creams in the shop, and $K$ is the number of ice-creams you want to buy. Then a line follows containing $N$ integers $C_1, \\\\\\\\cdots, C_N$ ($0 <= C_i <= 10^9$), in which $C_i$ is the number of calories in the $i^(t h)$ ice-cream. Then a line follows containing $N$ integers $H_1, \\\\\\\\cdots, H_N$ ($0 <= H_i <= 10^9$), in which $H_i$ is the happiness value of the $i^(t h)$ ice-cream.\n\n## Output\n\nFor each test case, print a single line containing two space-separated integers representing the calories of the densest ice-cream you will buy and the total happiness of the ice-creams you will buy, respectively.Remember that your goal is to buy $K$ ice-creams such that the calories of the densest ice-cream (the one with most calories) are as minimal as possible. If there is more than one way to do that, you want to maximize the total happiness of the ice-creams you will buy.\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:  \n- Let $ N \\in \\mathbb{Z} $ be the number of distinct stars.  \n- Let $ L, R \\in \\mathbb{Z} $ with $ 1 \\leq L \\leq R \\leq 10^{18} $ be the inclusive bounds for the area.  \n- Let $ P = \\{ (x_i, y_i) \\in \\mathbb{Z}^2 \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of star coordinates.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified} $  \n2. For each test case:  \n   - $ 1 \\leq N \\leq 1000 $  \n   - $ 1 \\leq L \\leq R \\leq 10^{18} $  \n   - $ |x_i|, |y_i| \\leq 10^9 $ for all $ i \\in \\{1, \\dots, N\\} $  \n   - All points in $ P $ are distinct.\n\n**Objective**  \nCount the number of unordered triplets $ \\{A, B, C\\} \\subseteq P $, $ | \\{A, B, C\\} | = 3 $, such that:  \n- The triangle $ \\triangle ABC $ is right-angled.  \n- The area $ \\mathcal{A} $ of $ \\triangle ABC $ satisfies $ L \\leq \\mathcal{A} \\leq R $.  \n\nThe area of a triangle with vertices $ A = (x_1, y_1) $, $ B = (x_2, y_2) $, $ C = (x_3, y_3) $ is:  \n$$\n\\mathcal{A} = \\frac{1}{2} \\left| (x_2 - x_1)(y_3 - y_1) - (x_3 - x_1)(y_2 - y_1) \\right|\n$$  \nA triangle is right-angled if the dot product of two of its side vectors is zero.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10199I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}