Well, I have a bunch of NiMH (Nickel Metal Hydride) batteries laying around from another project (don't ask). These AA batteries I have came from Amazon.com at $2 bucks, each. I think I bought three dozen to get that price.
Anyway, the four junk NiCd batteries are C size, but only 2/3 height, rated at 1400 mA-h. So, my 2500 mA-h AA batteries are going to be much more capable. Plus, the NiMH have a much better discharge curve that Ni-Cd.