Make Many Buri-Oden

各セットは必ず$1$個以上のぶりとおでんを含んでいることから， $1$個しかセットを買わない，または$1$個も買わないという選択は最適とはなりえません．

よって，この問題は以下の問題に帰着させることができます．

$N$項からなる正整数列$\{a_i\}_{i=1}^{N},\{b_i\}_{i=1}^{N}$が与えられます．

• $\min_{1 \leq i \leq j \leq N} \{a_i+a_j,b_i+b_j \}$

の最大値を求めてください．

まず買うセットを$1$つ固定します(便宜上$i$個目とします)． 次に以下の判定問題を解くことを考えます．

• $\min \{ a_i+a_j , b_i+b_j\} \geq x$となる$j$は存在するか？

これは$x$の大きさ対して単調性があるので， 条件を満たす$a_j,b_j$の値を効率よく取得することができれば 二分探索により高速に求めることができます．

最後に上の太字の部分を考えてみましょう．
$\min \{ a_i+a_j , b_i+b_j\} \geq x \Rightarrow a_i+a_j \geq x$かつ$b_i+b_j \geq x$であることから， 条件を満たす$j$は$b_j \geq \max \{ 0, x-b_i\}$を満たすものの中で， $a_j \geq \max \{0, x-a_i\}$を満たすものということができます． これは2項演算を$\max\{ \bullet , \bullet \}$とするセグメント木によって高速に求めることができます．

以上の議論により，$i$を$1$つ決めうった時に達成することのできる最大値を高速に求めることができたので， あとはすべての$i$に対して同様の操作をすればよいです．

時間計算量は$M:= \max \{a_1,a_2,\cdots , a_N, b_1 ,b_2, \cdots ,b_N\}$ として$O(N(\log(M))^2)$です．

余談：かなり実行時間カツカツで， Pythonでやると入力で重いかなと思いこのような入力形式をとりました． やりづらかったらすみません．