Here is a 5x4 rectangular wordsearch (area 20) containing the primes between 1 and 100,
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
(numbers in any direction or diagonal/backwards, overlaps permitted (17 = 7,17,71))
15414
29763
38310
05100
It has a score of "4" because we were able to pack 4 unused zeros in there.
We can't make a 3x3 wordsearch as there are too many digits due to the '11';
in theory, the highest score we can get is "2" with a 3x4 wordsearch (area 12):
112
345
678
900
But this is missing primes like "23", so is invalid.
Without using a computer:
What is the minimum possible area for a valid rectangular wordsearch?
For a wordsearch with that area, what is the highest possible score you can find?
Provide an example.
Proof of optimality would be a bonus, by hand (preferred) or computer (acceptable), but I don't know if a proof beyond brute force exists, so am less concerned with that, although it would be interesting.