The sad thing is, even being told in advance what the melody is, I still have difficulty recognizing it.

Changing the beat, the scale and the chords probably doesn't help.

(Great artists steal. Therefore, theft is great art. This is fallacious, but you get more songs that way.)