I just went through this last week and the trick was getting my finance director to tell HR that she approved the higher amount I wanted to offer. HR will play games with your budget until you take the excuse away.
We have history if you couldn't tell.