{"problem":{"name":"Max GCD","description":{"content":"We have a sequence of $N$ integers: $A_1, A_2, \\cdots, A_N$. You can perform the following operation between $0$ and $K$ times (inclusive): *   Choose two integers $i$ and $j$ such that $i \\neq j$, e","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc136_e"},"statements":[{"statement_type":"Markdown","content":"We have a sequence of $N$ integers: $A_1, A_2, \\cdots, A_N$.\nYou can perform the following operation between $0$ and $K$ times (inclusive):\n\n*   Choose two integers $i$ and $j$ such that $i \\neq j$, each between $1$ and $N$ (inclusive). Add $1$ to $A_i$ and $-1$ to $A_j$, possibly producing a negative element.\n\nCompute the maximum possible positive integer that divides every element of $A$ after the operations. Here a positive integer $x$ divides an integer $y$ if and only if there exists an integer $z$ such that $y = xz$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 500$\n*   $1 \\leq A_i \\leq 10^6$\n*   $0 \\leq K \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $A_2$ $\\cdots$ $A_{N-1}$ $A_{N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc136_e","tags":[],"sample_group":[["2 3\n8 20","7\n\n$7$ will divide every element of $A$ if, for example, we perform the following operation:\n\n*   Choose $i = 2, j = 1$. $A$ becomes $(7, 21)$.\n\nWe cannot reach the situation where $8$ or greater integer divides every element of $A$."],["2 10\n3 5","8\n\nConsider performing the following five operations:\n\n*   Choose $i = 2, j = 1$. $A$ becomes $(2, 6)$.\n*   Choose $i = 2, j = 1$. $A$ becomes $(1, 7)$.\n*   Choose $i = 2, j = 1$. $A$ becomes $(0, 8)$.\n*   Choose $i = 2, j = 1$. $A$ becomes $(-1, 9)$.\n*   Choose $i = 1, j = 2$. $A$ becomes $(0, 8)$.\n\nThen, $0 = 8 \\times 0$ and $8 = 8 \\times 1$, so $8$ divides every element of $A$. We cannot reach the situation where $9$ or greater integer divides every element of $A$."],["4 5\n10 1 2 22","7"],["8 7\n1 7 5 6 8 2 6 5","5"]],"created_at":"2026-03-03 11:01:13"}}