There will be more human troops available on Debir (in castle and the nearby monastery) when you obtain the second, fourth and sixth stones.
Go to Bolo and sneak! You can lure enemies away, then run around to grab the non-map treasures they are guarding. You can kite your way to the amulet in the mines on Bolo (1 boss, 3 minions wandering about). Remember to use the amulet before returning it to the priestess in Debir!
That will get you the second stone (you get the first for free when you arrived), so you will have more paladins to hire.
|