One quick remark: the upper bound will be $$ O\left(\min_j \frac{1}{H^2(p_j,q_j)}\right) $$ where $H$ is the Hellinger distance, not TV (we have $H^2\lesssim TV \lesssim H$). The sample complexity of simple hypothesis testing is captured by Hellinger, not total variation.
(I suspect this is tight on an instance-per-instance basis as well, but don't have a proof.)