You're trying to buy champagne on a beer budget.
There are few pocketable advanced P&S cameras with zooms and aperture-priority autoexposure. Actually, I would say none.
If you forego the aperture-priority autoexposure, you ought to check out the Olympus Epic Stylus Zoom (the black model), which had a 35-70 lens. Also, the Rollei Prego 70 has a 35-70 lens.
Among fixed-lens cameras, there are a bunch from the 1970s. I like the Olympus 35 RC, which has shutter-priority autoexposure or all-manual exposure.
If you can adapt to its quirks, the Rollei 35 cameras are excellent choices, although you probably will NOT find one for less than $100.