{"problem":{"name":"Ex - Linear Maximization","description":{"content":"There is a set $S$ of points on a two-dimensional plane. $S$ is initially empty. For each $i = 1, 2, \\dots, Q$ in this order, process the following query. *   You are given integers $X_i, Y_i, A_i$, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc244_h"},"statements":[{"statement_type":"Markdown","content":"There is a set $S$ of points on a two-dimensional plane. $S$ is initially empty.\nFor each $i = 1, 2, \\dots, Q$ in this order, process the following query.\n\n*   You are given integers $X_i, Y_i, A_i$, and $B_i$. Add point $(X_i, Y_i)$ to $S$, and then find $\\displaystyle \\max_{(x,y) \\in S}\\left{A_ix + B_iy\\right}$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1≤Q≤2 \\times 10^5$\n*   $|X_i|, |Y_i|, |A_i|, |B_i| ≤10^9$\n*   If $i ≠ j$, then $(X_i, Y_i) ≠ (X_j, Y_j)$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$Q$\n$X_1$ $Y_1$ $A_1$ $B_1$\n$X_2$ $Y_2$ $A_2$ $B_2$\n$\\vdots$\n$X_Q$ $Y_Q$ $A_Q$ $B_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc244_h","tags":[],"sample_group":[["4\n1 0 -1 -1\n0 1 2 0\n-1 0 1 1\n0 -1 1 -2","\\-1\n2\n1\n2\n\n*   When $i = 1$: add point $(1, 0)$ to $S$, then it will become $S = {(1, 0)}$. For $(x, y) = (1, 0)$, we have $-x - y = -1$, which is the maximum.\n*   When $i = 2$: add point $(0, 1)$ to $S$, then it will become $S = {(0, 1), (1, 0)}$. For $(x, y) = (1, 0)$, we have $2x = 2$, which is the maximum.\n*   When $i = 3$: add point $(-1, 0)$ to $S$, then it will become $S = {(-1, 0), (0, 1), (1, 0)}$. For $(x, y) = (1, 0)$ or $(x, y) = (0, 1)$, we have $x + y = 1$, which is the maximum.\n*   When $i = 4$: add point $(0, -1)$ to $S$, then it will become $S = {(-1, 0), (0, -1), (0, 1), (1, 0)}$. For $(x, y) = (0, -1)$, we have $x - 2y = 2$, which is the maximum."],["9\n-1 4 -8 -2\n9 -9 -7 7\n4 1 6 7\n-4 -1 -4 -5\n-9 3 -2 -6\n-1 0 -8 5\n-8 -5 0 0\n8 3 0 -4\n2 -5 2 5","0\n35\n31\n21\n36\n87\n0\n36\n31"]],"created_at":"2026-03-03 11:01:14"}}