{"raw_statement":[{"iden":"statement","content":"Engineers around the world share a lot of common characteristics. For example, they're all smart, cool and extremely lazy!\n\nAsem is a computer engineer, so he is very lazy. He doesn't leave the house for weeks. Not even for a shisha with his best friends. \n\nOne day his mother insisted that he goes to the park to get some fresh air. Asem is a lazy but a very practical person. He decided to use the time spent on the way to the park to test his new device for detecting wireless networks in the city. The device is as much advanced as it's weird. It detects a network if the coverage area of the network is entirely inside the coverage area of the device. Both the coverage area of the wireless networks and Asem's device are circular shaped. \n\nThe path between Asem's house and the park is a straight line and when Asem turn on the device, it display one integer on its screen, the sum of the radiuses of the detected networks.\n\nGiven the coordinates of the center of the networks coverage area and their radiuses, what is the maximum number that could be displayed on the screen knowing that Asem can test the device anywhere in the street?\n\nThe first line of the input will contain T the number of test cases.\n\nEach test case starts with two integers on a single line (0 < N ≤ 105), the number of wireless networks, (0 < M ≤ 109), the radius of the coverage area of Asem's device.\n\nThen N lines follow, each describes a wireless network and contains three integers ( - 109 ≤ xi ≤ 109), the X coordinate of the center of the i'th network coverage area,( - 109 ≤ y ≤ 109), the Y coordinate of the center of the i'th network coverage area, (1 ≤ ri ≤ 109), the radius of the i'th network coverage area. Where the street is the X-axis here and Asem can test the device anywhere on it.\n\nFor each test case print one integer. The maximum number that could be displayed on the screen.\n\nLarge I/O files. Please consider using fast input/output methods.\n\nThe figure shows a possible solution for the first sample.\n\n"},{"iden":"input","content":"The first line of the input will contain T the number of test cases.Each test case starts with two integers on a single line (0 < N ≤ 105), the number of wireless networks, (0 < M ≤ 109), the radius of the coverage area of Asem's device.Then N lines follow, each describes a wireless network and contains three integers ( - 109 ≤ xi ≤ 109), the X coordinate of the center of the i'th network coverage area,( - 109 ≤ y ≤ 109), the Y coordinate of the center of the i'th network coverage area, (1 ≤ ri ≤ 109), the radius of the i'th network coverage area. Where the street is the X-axis here and Asem can test the device anywhere on it."},{"iden":"output","content":"For each test case print one integer. The maximum number that could be displayed on the screen."},{"iden":"note","content":"Large I/O files. Please consider using fast input/output methods.The figure shows a possible solution for the first sample.  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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 wireless networks.  \n- Let $ M \\in \\mathbb{Z}^+ $ be the radius of Asem’s device.  \n- For each network $ i \\in \\{1, \\dots, N\\} $, let $ (x_i, y_i, r_i) \\in \\mathbb{Z}^3 $ denote the center coordinates and radius of the $ i $-th network’s coverage circle.  \n\nThe street is the $ x $-axis. Asem’s device is a circle of radius $ M $, centered at some point $ (p, 0) \\in \\mathbb{R} \\times \\{0\\} $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{large} $  \n2. $ 1 \\le N \\le 10^5 $  \n3. $ 1 \\le M \\le 10^9 $  \n4. $ -10^9 \\le x_i, y_i \\le 10^9 $  \n5. $ 1 \\le r_i \\le 10^9 $  \n\n**Objective**  \nFind the maximum possible sum of radii $ \\sum_{i \\in S} r_i $, where $ S \\subseteq \\{1, \\dots, N\\} $ is the set of networks whose coverage circles are entirely contained within *some* placement of Asem’s device circle (centered at $ (p, 0) $, radius $ M $).  \n\nA network $ i $ is detectable by a device centered at $ (p, 0) $ if and only if:  \n$$\n\\sqrt{(x_i - p)^2 + y_i^2} + r_i \\le M\n$$  \n\nEquivalently, for fixed $ i $, the set of valid $ p \\in \\mathbb{R} $ such that network $ i $ is detected is:  \n$$\np \\in \\left[ x_i - \\sqrt{M^2 - y_i^2},\\ x_i + \\sqrt{M^2 - y_i^2} \\right] \\quad \\text{if } |y_i| \\le M\n$$  \n(Otherwise, no $ p $ detects network $ i $.)\n\nThus, each network $ i $ with $ |y_i| > M $ is **never** detectable.  \nFor networks with $ |y_i| \\le M $, define the interval:  \n$$\nI_i = \\left[ x_i - \\sqrt{M^2 - y_i^2},\\ x_i + \\sqrt{M^2 - y_i^2} \\right]\n$$  \n\nThe problem reduces to:  \n> Find a point $ p \\in \\mathbb{R} $ that lies in the maximum-weight union of intervals $ I_i $, where the weight of interval $ I_i $ is $ r_i $.  \n> That is, maximize $ \\sum_{i: p \\in I_i} r_i $ over $ p \\in \\mathbb{R} $.  \n\n**Objective (Formal)**  \n$$\n\\max_{p \\in \\mathbb{R}} \\sum_{\\substack{i=1 \\\\ |y_i| \\le M \\\\ p \\in I_i}}^{N} r_i\n$$","simple_statement":"Asem walks along the x-axis with a device of radius M.  \nFor each Wi-Fi network (center at (x_i, y_i), radius r_i), his device detects it if the entire network circle is inside his device’s circle.  \nFind the maximum possible sum of radii of all detectable networks, by choosing the best position for his device on the x-axis.","has_page_source":false}