Better method to count records in Custom Paging for SQL Server 2005

heres my problem, since I migrated to SQL-Server 2005, I was able to use theRow_Number() Over Method to make my Custom Paging Stored Procedure better. But theres onte thing that is still bothering me, and its the fact the Im still using and old and classic Count instruction to find my total of Rows, which slow down a little my Stored Procedure. What I want to know is: Is there a way to use something more efficiant to count theBig Total of Rows without using the Count instruction? heres my stored procedure:

SELECT RowNum, morerecords, Ad_Id FROM (Select ROW_NUMBER() OVER (ORDER BY Ad_Id) AS RowNum,morerecords = (Select Count(Ad_Id) From Ads) FROM Ads) as test
WHERE RowNum Between 11 AND 20

The green part is the problem, the fields morerecords is the one Im using to count all my records, but its a waste of performance to use that in a custom paging method (since it will check every records, normally, theres a ton of condition with a lot of inner join, but I simplified things in my exemple)...I hope I was clear enough in my explication, and that someone will be able to help me. Thank for your time.

Well, since you want to join a single value (the row count) of a table with other columns from the table, the single value must be returned as a result set from a subquery or a join table. If you don't like using count(Ad_Id) to get the row count, you can join the sysindexes table to get the row count for a specific table. For example:

SELECT RowNum, morerecords, Ad_Id,RowCnt
FROM (Select ROW_NUMBER() OVER (ORDER BY Ad_Id) AS RowNum
FROM Ads) as test,sysindexes s
WHERE RowNum Between 11 AND 20
and s.id=object_id('Ads')
and s.indid=(select min(indid)
from sysindexes where id=object_id('Ads'))

If you have a cluster index on the table, you can replace the green part with 1.