A single 4PST relay is about the same price, but more compact, than 4 separate "ordinary" SPST ones, or 2 * DPST as an intermediate solution.
( http://www.newark.com/panasonic-ew/s4eb-12v/power-relay-4pst-12vdc-4a-pc-board/dp/46F5824 )
If you need a 2PST per line, I'd go for four relays anyway.
Edit: oops, you need 5V relays, so there's not too much choice 