\(t\) として考えるべきは有理数だけです．

\(t=q/p\) (既約分数) とします． ここで，\(p\) が奇数 \(r\) (\(3 \leq r\))を約数に持つとします． ここで，正整数 \(k\) であって，\(k \times 2^L+1 \equiv 0 \mod{r}\) を満たすものが必ず取れます．

\(t'=(k \times 2^L+1)t\) としてみます． すると，\(A_i+V_it \equiv 0 \mod{2^L} \rightarrow A_i + V_i t'=A_i+V_it+k \times 2^L \times (V_i \times t) \equiv 0 \mod{2^L}\) です． よって，\(t\) の代わりに \(t'\) を用いることで，獲得する寿司を減らすこと無く，\(t\) の分母から奇数の因数をなくすことができます．

結局，\(t\) の分母としては \(2\) 冪だけを考えればよいです．

\(A_i+V_it \equiv 0 \mod{2^L}\) になる条件を考えます． \(V_i=2^w \times u\) (\(u\) は奇数) と分解したとします． ここで，\(t=q/2^w\) と書いてよいです．これは既約分数であるとは限らないことに注意してください． すると \(q\) の条件は，\(A_i+u \times q \equiv 0 \mod{2^L}\) となり，\(q \mod{2^L}\) に関する条件が得られます．

最終的に得られる \(t\) の条件は以下のようになります．

• \(t\) を \(2\) 進表記（小数点以下も含む）することを考える．
• \(t\) の \(2^{0-w},2^{1-w},\cdots,2^{L-1-w}\) の桁は指定されている．
• \(2^{0-w}\) より下の桁はすべて \(0\)
• \(2^{L-1-w}\) より上の桁は自由

この条件は，Binary-Trie を使うと簡潔に書けます． 下の桁ほど Binary-Trie の根に近くなるようにすると，\(t\) の条件は，ある部分木に含まれる，と言い換えられます．

ここまでくればあとは簡単です． すべての \(i\) について \(t\) の条件を列挙して，獲得する価値の総和が最大化される Binary-Trie の頂点を見つければよいです．

計算量は全体で \(O(NL)\) になります．

解答例(c++)