Railway network of one city consists of (n) stations connected by (n-1) roads. These stations and roads forms a tree. Station (1) is a city center. For each road you know the time trains spend to pass this road. You can assume that trains don't spend time on stops. Let's define (dist(v)) as the time that trains spend to get from the station (v) to the station (1). This railway network is splitted into zones named by first (k) capital latin letters. The zone of the (i)-th station is (z_i). City center is in the zone A. For all other stations it is guaranteed that the first station on the road from this station to the city center is either in the same zone or in the zone with lexicographically smaller name. Any road is completely owned by the zone of the most distant end from the city center. Tourist will arrive at the airport soon and then he will go to the city center. Here's how the trip from station (v) to station (1) happends: At the moment (0), tourist enters the train that follows directly from the station (v) to the station (1). The trip will last for (dist(v)) minutes. Tourist can buy tickets for any subset of zones at any moment. Ticket for zone (i) costs (pass_i) euro. Every (T) minutes since the start of the trip (that is, at the moments (T, 2T, \ldots)) the control system will scan tourist. If at the moment of scan tourist is in the zone (i) without zone (i) ticket, he should pay (fine_i) euro. Formally, the zone of tourist is determined in the following way: If tourist is at the station (1), then he already at the city center so he shouldn't pay fine. If tourist is at the station (u \neq 1), then he is in the zone (z_u). If tourist is moving from the station (x) to the station (y) that are directly connected by road, then he is in the zone (z_x). Note, that tourist can pay fine multiple times in the same zone. If tourist is at the sta