You'll have to be patient for a while.
It's not in the tower.
You'll have to find the castle floors.
On the main floor, initially only one room will open.
A bag can be found there.