Fully depends on your in-map features. If it is a free-roam adventure, then a big map will be necessary. If it is a 'path-made' map where you are directed along a set path along your short adventure, then a small map is all you need.
It will be a branched path map, CTM -w- a story. I could easily use 3000x3000.
Branching story map? You sure it can fit in a 3000x3000? XD I say break the rules and REALLY tear it up with a massive adventure map. Now, don't make the plot the same, but make it like the Stanley parable, with ALOT of replay value and many hidden endings that will keep people guessing.