Let $X_1,\dotsc, X_n$ be $n$ i.i.d. random variables where $X_1 \in [a,b]$. Similarly, let $Y_1,\dotsc,Y_m$ be $m$ i.i.d. random variables where $Y_1 \in [c,d]$. Furthermore, $X_i$ and $Y_j$ are independent for all $i \in \{1,\dotsc,n\}$ and $j \in \{1,\dotsc,m\}$. Intuition tells me that for any $\delta \in (0,1)$ it should hold that:
$$
\Pr \left (\mathbf{E}[X_1+Y_1] > \frac{1}{n} \sum_{i=1}^n X_i + \frac{1}{m} \sum_{i=1}^m Y_i - (b-a + d-c)\sqrt{\frac{\ln(1/\delta)}{2\min\{n,m\}}} \right )\geq 1-\delta.
$$
How do I go about showing this? It really is true, right? Intuition says that it is true because if we paired up points, $X_i$ and $Y_i$ until we ran out of one type, we could get from Hoeffding's inequality that with probability at least $1-\delta$:
$$
\mathbf{E}[X_1+Y_1] > \frac{1}{\min\{n,m\}} \left (\sum_{i=1}^{\min\{n,m\}} X_i+Y_i \right ) - (b+d - (a+c))\sqrt{\frac{\ln(1/\delta)}{2\min\{n,m\}}}.
$$
The first equation is the same, except that it uses *more* samples of one of the random variables ($X$ or $Y$).

I have tried bounding $\mathbf{E}[X_1]$ and $\mathbf{E}[Y_1]$ independently and then using a union bound. I get the top equation, but with $\ln(2/\delta)$ rather than $\ln(1/\delta)$.