LIKE and REGEX optimization

Hi all.

I have a database with 62 million registers and I have to make a
SELECT using LIKE.

This is my select:
SELECT * FROM phone WHERE name LIKE = '%ZANINETTI%' AND city = 'SAO
PAULO' AND state = 'SP'

I have an index created like this:
CREATE INDEX "telefones_idx2" ON "public"."phone"
  USING btree ("name" varchar_pattern_ops, "city", "state");

When I explain the query I have this:
QUERY PLAN
Bitmap Heap Scan on telefones  (cost=1031528.27..2726942.75 rows=4
width=145)
  Recheck Cond: (((city)::text = 'SAO PAULO'::text) AND ((state)::text
= 'SP'::text))
  Filter: ((name)::text ~~ '%ZANINETTI%'::text)
  ->  Bitmap Index Scan on telefones_idx2  (cost=0.00..1031528.27
rows=1712760 width=0)
        Index Cond: (((city)::text = 'SAO PAULO'::text) AND
((state)::text = 'SP'::text))


The cost is over than 1 million! It's to high and I have to reduce it.
Does someone know how can I make it?

Thanks in advance.

Kico Zaninetti
carpe diem