Ubuntu – Fresh installation of ubuntu 16.04 gives me warning about locale. Unable to fix

I got this on a fresh installation of Ubuntu 16.04 on AWS Lightsail

_____________________________________________________________________
WARNING! Your environment specifies an invalid locale.
 The unknown environment variables are:
   LC_CTYPE=UTF-8 LC_ALL=
 This can affect your user experience significantly, including the
 ability to manage packages. You may install the locales by running:

   sudo apt-get install language-pack-UTF-8
     or
   sudo locale-gen UTF-8

To see all available language packs, run:
   apt-cache search "^language-pack-[a-z][a-z]$"
To disable this message for all users, run:
   sudo touch /var/lib/cloud/instance/locale-check.skip
_____________________________________________________________________

Then I follow the instructions

$ sudo apt-get install language-pack-UTF-8
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Unable to locate package language-pack-UTF-8

Then I tried the other one

$ sudo locale-gen UTF-8
Error: 'UTF-8' is not a supported language or locale

What should I do now?