NG Pairs

果物を $1$ つまたは $2$ つ選ぶ、とすると大変なので、どの果物と組み合わせてもよいおいしさ $0$ の果物 $0$ があるとして、 $N + 1$ 個の果物から必ず $2$ 個選ぶことを考えましょう。
考えられる果物の組合せは $O(N^2)$ 通りですが、そのうち禁止された組合せは $M$ 通りしかありません。よって、おいしさの合計の大きい順、すなわち $A_i + A_j$ の大きい順に $M + 1$ 組を列挙できれば、鳩ノ巣原理より少なくとも $1$ つ禁止されていない組合せがあります。
例えば $2$ 分探索を使うなどして、 $A_i + A_j \geq K$ を満たす $(i ,j)$ の組が $M + 1$ 個以上となるような最大の $K$ を探し、合計が $K$ 以上となる組み合わせを全探索するといった解法があります。これは、適切に実装すれば $O((N + M) \log \max(A))$ などの計算量になります。