How bad is flush_rules() on init hook?

According to the Codex:

[...] This function can be extremely costly in terms of performance. It should be used as sparingly as possible - such as during activation or deactivation of plugins or themes. Every attempt should be made to avoid using it in hooks that execute on each page load, such as init.

Ok, so, I know it shouldn't be used in every page load, but I still needed a very conditional rewrite rule on this project. I have these 2 url structures:

 - http://ift.tt/1zAnJrX //This is a product url, here I expect the normal behavior from wp.

 - http://ift.tt/1ArWanD //This should be some kind of a filter, where the site gets all the tables related to the office department. Note how both URL structure matches.

To make it work, I narrowed it down to these very specific URLs, using some regex. If matched, I'll run 2 queries to verify if the url I'm in is for the filter I want that rule to apply, or if it's a product url. In the latter, I want wordpress to behave normally. But I have to flush the rules either way, whether it's a product or it's the category and the filter, so that both pages work properly and dinamically.

I do all this to narrow down the use of this function to the least possible, but the Codex doesn't really tell me how bad it does affect the performance, or why. I'm passing the parameter on that function as false by the way, so it doesn't rewrite my htaccess file, but I'm not sure where that rewrite rule option is stored, if it's on the memory somewhere, or on the database, wish they would provide some clarification on that.

Thanks in advance for reading this question. Any pointers are appreciated here, even if you want to point me to some other way of doing this. :)