Where can I find a bag?

Hint 1 of 6:

You'll have to be patient for a while.

Hint 2 of 6:

It's not in the tower.

Hint 3 of 6:

You'll have to find the castle floors.