I did not understand

Does the background need to follow the palette?

Or can I be free to use anything on it?

the background can be a different colour to the three you chose for all intractable objects, or in other words you can use four colours.