How to generate random pair less than several pairs in a given list in python

Given an L list with several elements as [n1,n2], I want to generate a random [i,j] pair such that i < n1 or j < n2 for all [n1,n2] in L. (i,j >= 1, but this is a minor detail.)

For instance, L = [[5, 3], [3, 7], [2, 11], [4, 6]], so if you think of this as part of a (max_first_in_L) by (max_second_in_L) "rectangle" (the +s denote the elements in L):

0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 +
0 0 0 0 0 0 +
0 0 0 0 0 +
0 0 +

I want to get the coordinates of a random zero, such as 1 = [2, 4].

My approach was to generate a list of all coordinate-pairs in the L-rectangle, remove all that are to the right and below the elements in L, and choose a random element from the remaining. If the L-rectangle is large - say, 2000 by 2000 -, this would create a 4_000_000 element long list, which is a bit hard on memory. Plus the removal.

I believe the optimal approach would be using indices and not creating large lists, but I haven't figured out how to do that.

Any help is greatly appreciated. (If possible, not using modules, or only basic ones.) In case this has already been asked before (to my knowledge, it hasn't), please point me in the right direction.

(Disclaimer: this is my first time using this platform and I'm a Python beginner. Pardon me for any mistakes I may have made in the posting of this question.)