Backpackers in Paia is $25 a night in the dorm rooms (rainbowsurf hostel),

iv'e got a unit at the luna lodge in paia for $55 a night

will have a few beers with you divaldo (we better get a few practice ones in at Robe )
also Try VRBO.com there is a good selection of places there.