青木君、すぬけ君への贈り物の候補の価値の多重集合をそれぞれ \(S,T\) とします。（同じ相手への同じ価値の贈り物の候補が複数あっても明らかに意味はないため多重集合を集合と置き換えても問題ありませんが、ここでは実装の都合上多重集合とします。）

このとき、次のような手順を繰り返す事で問題を解く事ができます。

1. \(S,T\) の要素のうち最大のものをそれぞれ \(s_0,t_0\) とします。 （ここで、最大のものを選べない、すなわち、\(S,T\)のいずれかが空集合の時、高橋君は明らかに条件をみたすように贈り物を選ぶことはできません。そのような場合は \(-1\) を出力し、繰り返しを終了します。）

2. \(\lvert s_0-t_0\rvert \leq D\) のとき、\(S,T\) の他の要素の値によらず \(s_0+t_0\) が問題の答えとなります。よって、 \((s_0+t_0)\) を出力し、繰り返しを終了します。

3. そうでないとき、\(s_0,t_0\) の大小によって場合分けを行います。(ここで 2. より、\(s_0\neq t_0\) であることに注意してください。)
   \(s_0<t_0\) のとき、\(S\) の任意の要素 \(s\) について、 \(s<t_0\) であり、\(\lvert s-t_0\rvert=t_0-s\geq t_0-s_0>D\) となるため、すぬけ君に価値 \(t_0\) の贈り物を贈り、かつ条件をみたすように贈り物を選ぶことはできません。よって、この時の答えは、すぬけ君への贈り物の候補の価値の多重集合が、 \(T\) から 要素 \(t_0\) を除いた(多重)集合 \(T'\) であった時の答えと一致します。よって、\(T\) から \(t_0\) を取り除き、1. に戻ります。
   \(s_0>t_0\) のときも同様に、\(S\) から \(s_0\) を取り除き、1. に戻ります。

一連の手順(1.-3.) を行うたびに、\(S\) と \(T\) の要素数の和は \(1\) ずつ減っていくため、この手順は高々 \(N+M\) 回の繰り返しで終了します。

さらに、最初に \(A.B\) をソートした列を持っておくと、1. での各集合の最大値の参照は末尾の参照に対応し、3.でのいずれかの集合における最大値の削除は末尾の削除に対応するため、これはvectorなどで \(O(1)\) で 行う事ができます。

よって、ソートに必要な計算量 \(O(N\log N+M\log M)\) とあわせて全体で計算量は \(O(N\log N+M\log M)\) であり、十分高速にこの問題を解く事ができました。

c++による実装例:

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)


int main(void){
	int n,m;
	long long d,x,y;

	cin>>n>>m>>d;
	vector<long long>a(n),b(m);

	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++)cin>>b[i];
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());

	while(true){
		if((n==0)||(m==0)){
			cout<<-1<<endl;
			return 0;
		}
		x=a.back(),y=b.back();
		if(abs(x-y)<=d){
			cout<<(x+y)<<endl;
			return 0;
		}
		if(x>y)a.pop_back(),n--;
		else b.pop_back(),m--;
	}

	return 0;
}