{"problem":{"name":"Squared Norm Maximization","description":{"content":"You are given $N$ pairs of integers $(A_1,B_1),(A_2,B_2),\\cdots,(A_N,B_N)$. For a subset $s$ of ${1,2,\\cdots,N}$, we define its **score** as follows: *   $(\\sum_{i \\in s} A_i)^2 + (\\sum_{i \\in s} B_i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc076_e"},"statements":[{"statement_type":"Markdown","content":"You are given $N$ pairs of integers $(A_1,B_1),(A_2,B_2),\\cdots,(A_N,B_N)$.\nFor a subset $s$ of ${1,2,\\cdots,N}$, we define its **score** as follows:\n\n*   $(\\sum_{i \\in s} A_i)^2 + (\\sum_{i \\in s} B_i)^2 - 3 \\sum_{i \\in s} (A_i^2+B_i^2)$\n\nFind the maximum possible value of the score.\nSolve $T$ cases for one input.\n\n## Constraints\n\n*   $1 \\leq T \\leq 250000$\n*   $1 \\leq N \\leq 250000$\n*   $\\sum_{1 \\leq i \\leq N} |A_i| \\leq 10^9$\n*   $\\sum_{1 \\leq i \\leq N} |B_i| \\leq 10^9$\n*   The sum of $N$ over the $T$ cases is at most $250000$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc076_e","tags":[],"sample_group":[["4\n4\n1 0\n0 1\n-1 0\n0 -1\n4\n1 0\n1 0\n1 0\n1 0\n6\n1 -9\n-7 -2\n0 -10\n10 1\n2 -8\n1 -8\n10\n19271058 -140039457\n-3441379 -134156148\n227767903 -70474702\n-837477 -74699717\n153584327 80404336\n115741008 -22141349\n-190028077 -21940357\n76149725 17176032\n159846847 -296045185\n-53332199 142922717","0\n4\n296\n178262497119089558\n\nIn the first case, if $s={}$, the score is $0$, which is the maximum.\nIn the second case, if $s={1,2,3,4}$, the score is $4$, which is the maximum."]],"created_at":"2026-03-03 11:01:14"}}