FactoryTruck

A factory truck can move along single straight road. There are n special places on the straight road, the distance between each pair of adjacent places is exactly 1000 meters. In each place there is one freight or one container. There are 26 different types of freights, they are described by lowercase letters ('a'-'z'). There are 26 different types of containers, they are described by uppercase letters ('A'-'Z'). Each freight should be transported to a container of the correspondent type ('A' for 'a', 'B' for 'b', etc). Each container can hold only one freight of the correspondent type and no one others. Truck can move with the speed 1000 meters per minute, it takes one minute to load a freight on it, and it takes one minute to unload a freight from it. The truck can carry no more than one freight in any moment.

You are given a String initialState. The length of initialState is n. The i-th character of initialState describes the item on the i-th special place on the road. The lowercase letter means the type of freight, and the uppercase letter means the type of the container. Return the minimal time truck needs to transport all the freights or -1 if it is impossible.