Amazon VPS are commonly targeted by bots trying to brute force entry, so you need to use a strong password. My guess is that is what happened. A passphrase (rather than a password) is much better. Actually best of all, use SSH keys and disable password login altogether.

Having a poor password is a little like leaving the keys to your house under the front mat. It doesn't matter how good the deadbolts on your doors and windows are if the bad guys find the keys...

If you haven't done too much since the initial hack; then you may be able to go back through your bash history and see what was done to your server (and undo it). Otherwise there are a number of Linux server "anti-malware" tools you can use to clean up (e.g. Chkrootkit, Rootkit Hunter). Although personally; unless I can be 100% sure on what has been done then I can never 100% trust a server that has been compromised (even if it seems ok).

If you have a backup (e.g. TKLBAM) that predates the hack (and you won't lose much work/data/etc) then restoring to a new clean server would be advised. Even just restoring a current (cleaned) backup to a new server (using a good password, or better still keys) would be a reasonable idea IMO. At least that would eliminate the possibility of apt installed binaries being compromised. Obviously though your backup may well still include malware (which might also be reinstalled)...

Also if you contact Amazon and explain the situation perhaps they will give you a refund (or at least a partial refund)? Although seeing as they shut your server down and you restarted it (without resolving the issue) then they maybe not.