Try holding down C to boot from optical drive.
Once you have contact with the installer DVD you can format the HD (if it's properly connected). The easiest way should be to do a clean install, but you would be able to perform some advanced options like partitioning etc., if you need that for some reason...