How do I get my haversack back?

Hint 1 of 3:

Try bribery!

Hint 2 of 3:

Exchange the haversack for gold