Africa

Ryan's hometown is said to be an island somewhere in Africa. Lions are known to live mainly on the African grasslands, and unfortunately no African island has lions today or had them in the past, so the story that Ryan comes from an island is most likely someone's mistake. Africa has many lakes large enough to pass for a sea, so a lakeshore may also have been mistaken for an island.

The largest lake in Africa is Lake Victoria, which spans three East African countries: Uganda, Kenya, and Tanzania. It almost touches the Serengeti, a region that also straddles the border between Kenya and Tanzania. The Serengeti covers more than 30,000 square kilometers of grassland, savanna, and pasture, and a wide range of animals and plants live there. A safari tour of the Serengeti is often called the highlight of a trip to Africa. To protect nature, some areas may only be visited along fixed routes, and in return the natural state of the land is well preserved, which is why the region is famous. The grass on the plains is short, so animals are easy to spot, and the Serengeti is one of the places where all of the Big Five can be seen. The Big Five are the five kinds of animals that are hard to see on an African safari: the elephant, the rhinoceros, the buffalo, the leopard, and the lion. Many African countries have safaris, but few places let you see all of the Big Five.

Safari is the Swahili word for a journey, and it refers to a trip through a nature park to watch wild animals. Most countries that draw many travellers have safaris, and the style differs by region. There are also many ways to enjoy a safari: a game drive, where you watch animals from a vehicle, a boat safari along a river or lake, a walking safari on foot, and a night safari held after dark to see the animals that come out at night.

One famous safari is Etosha in Namibia. It became widely known two years ago when the travel show "Youth Over Flowers" aired an episode about Namibia. Unlike other safaris, you may drive your own vehicle there, which gives a great deal of freedom. The park has campsites, so you can travel for several days, and waterholes nearby let you see animals up close. The region is very dry, so animals gather at the waterholes scattered around the park to drink. Many species come, and even the rhinoceros, which is hard to see elsewhere, can be seen at the waterholes.

However, Namibia has no visa waiver agreement with Korea, so a traveller must obtain a visa before visiting Namibia. Korea has no Namibian embassy, so the traveller either enters another African country and gets the visa at the Namibian embassy there, or gets the visa through an agency. A visa through an agency costs 140 dollars, which is very expensive, so getting it locally is better for the budget, but there are very few places in Africa where a Korean can get a Namibian visa. Among the places many travellers visit, Cape Town in South Africa is practically the only one. So a traveller who does not visit South Africa before Namibia on the itinerary, or who cannot stay in Cape Town long enough for the visa to be issued, has to apply for the visa through an agency in Korea. If the itinerary visits South Africa at any point before Namibia, the traveller can get the visa in Cape Town, and the cost drops to a very cheap 40 dollars. From Cape Town you can reach Namibia by bus or by plane, so people travelling to Namibia usually enter through Cape Town, get the visa there, and then head to Namibia. In this problem, assume that the traveller can stay in Cape Town long enough whenever South Africa comes before Namibia on the itinerary.

Besides Namibia, many other African countries require a visa for entry. In the passport power ranking published every year, Korea usually holds a high position, and in the most recent 2018 ranking the Korean passport tied for first place with the Singaporean passport at 163 points. The score is the number of countries that can be visited without a visa. That count also includes countries where the visa is issued during entry with no need to obtain one in advance, so the number of countries with truly visa-free entry is smaller. Because a visa on arrival means that a passport alone is enough to enter with no other condition, it may seem reasonable to compare visa-on-arrival countries with visa-free countries. But a visa on arrival still costs a certain fee, so a traveller who has to watch the budget cannot ignore it. For example, to enter Kenya you pay 50 dollars for a single-entry visa or 100 dollars for a multiple-entry visa.

Among the African countries that Koreans often visit, South Africa and Botswana allow visa-free entry. South Africa allows a 30-day stay without a visa, and Botswana allows 90 days. Because South Africa sits at the southern tip of Africa and has many flights, it is often chosen as the first or the last stop of a trip across Africa. Botswana is a landlocked country in southern Africa and shares borders with South Africa, Namibia, and others. Botswana's famous attraction is Chobe National Park, also one of the well-known safaris, and what sets it apart is its boat safari. The park is in the north of Botswana, so it is convenient to visit together with Zambia or Zimbabwe, which touch Botswana's northern border. In other words, although Botswana is connected to South Africa by land, tourists rarely travel directly from South Africa to Botswana and mostly arrive from Namibia. The usual route runs from Windhoek, the capital of Namibia, to Maun, a city south of Chobe National Park. There used to be no scheduled bus, so travellers had to hitchhike, but a land route now runs on certain days of the week, which is said to have made the trip easier than before.

Maun in Botswana is the city most people visit on the way to the Okavango Delta. The delta was listed as a UNESCO World Natural Heritage site in 2014. It is a delta of wetlands and plains formed on the lower reaches of the Okavango River, and unlike an ordinary delta that forms where a river meets the sea, the Okavango Delta lies in the middle of the continent. Like the other nature parks of Africa, it is home to countless birds and wild animals. The first way to enjoy the Okavango Delta is a light-aircraft tour that views the whole delta from the sky. But you cannot see animals up close that way and it costs a great deal, so it is not the usual choice. The method most travellers choose is a mokoro tour, which travels the waterways in a mokoro, the traditional boat of the region. You can take a two-day trip that goes deep into the delta by mokoro, camps overnight, and returns, or a one-day trip. The river floods every year, so the wild animals you can see depend on when you go. In the dry season, from June to September, elephants, hippos, lions, and rhinoceroses are said to be easy to see.

From Maun, the gateway to the Okavango Delta, to Kasane in the north, the usual base for a Chobe safari, the straight-line distance is not great, but no road crosses Chobe National Park, so you have to go around by road. The trip takes almost a full day, so a traveller short on time may fly from Maun airport to Kasane airport. The flight runs twice a week, so anyone planning to take it has to plan around the days it operates. The flight takes one hour, while a car takes seven hours, and a bus or similar takes even longer.

Kasane is the northernmost city of Botswana, and right next to it is the point where the borders of four countries meet: Botswana, Namibia, Zambia, and Zimbabwe. Koreans enter both Zambia and Zimbabwe on a visa on arrival, so this is also a point where the visa plan depends on the order in which the countries are visited. In Zimbabwe a single-entry visa costs 30 dollars and a double-entry visa costs 45 dollars. In Zambia a single-entry visa costs 50 dollars and a double-entry visa costs 80 dollars. Victoria Falls, a landmark of Africa, sits on the border between Zambia and Zimbabwe, and to see the falls from both sides you have to cross the border. Fortunately, travellers who visit this way have one more option: the joint Zambia-Zimbabwe visa. With this visa you can move between Zimbabwe and Zambia without limit during the set period. However, once you move to a country other than Zambia or Zimbabwe, the visa is no longer valid. This visa costs 50 dollars, so a traveller who plans to visit both countries is better off with it. Choosing the order of the countries well therefore saves visa fees. So, given the order in which the countries are visited, we want to find the total visa fee. The explanation so far, combined with the introductions of the other countries and regions below, gives enough information to solve this. One could also think about inserting another country into the fixed order to reduce the cost, but we do not consider that here.

Victoria Falls, mentioned above, is the largest waterfall in Africa and lies on the Zambezi River between Zambia and Zimbabwe. The Scottish explorer Livingstone is said to have been the first European to find the falls, and he named them Victoria Falls after the British queen of the time. The falls are also listed as a UNESCO World Natural Heritage site, under the name Mosi-oa-Tunya with Victoria Falls listed alongside. Mosi-oa-Tunya is the local name for the falls and is said to mean the smoke that thunders. The towns on either side of the falls are Livingstone in Zambia and Victoria Falls in Zimbabwe. You can walk between the two towns, but since that crosses a border, you need the right visa. Zimbabwe is a very large country in southern Africa and is widely known for the Zimbabwean dollar, a currency that recorded enormous inflation. Today the country uses the US dollar. Its only well-known destination is Victoria Falls at its western edge, so most people visit on a day trip. Zambia, on the other hand, is a country you pass through on the way to East Africa, so many travellers also go to the region north of Livingstone.

To reach Tanzania, the East African country next to Zambia, travellers take the well-known TAZARA railway. The line connects New Kapiri Mposhi station in Zambia with Dar es Salaam station in Tanzania. The track is 1860 km long and the express train takes about 30 hours. Delays are said to be less common than before but still frequent, so anyone travelling by rail should leave slack in the schedule. Food and other goods are sold on the train, and because Zambia and Tanzania use different currencies, the currency you can use depends on where the train is at the time of purchase. At the border, an immigration officer boards the train and handles the paperwork in the compartments. If you hand over your passport and the visa fee, you receive a visa on arrival and may enter. The Tanzanian visa costs 50 dollars. A multiple-entry visa is available for 100 dollars.

The places most often visited in Tanzania are the Serengeti mentioned above, Zanzibar, and Kilimanjaro. Zanzibar is an island east of Tanzania, reached from Dar es Salaam by ferry or by plane. Because of its location it has been a trading port since long ago, and its history is very complex. Stone Town, the old town of Zanzibar, is a UNESCO World Heritage site. Many people go there to see the emerald water of the Indian Ocean and the white sand beaches.

Kilimanjaro is a volcano in northeastern Tanzania and the highest mountain in Africa. People usually think of Africa as a hot region, and the mountain is famous for the year-round snow on its summit, which contrasts with that image. (Of course, not all of Africa is hot.) The mountain is very high, and local rules allow climbing only with a guide, which is very expensive. Most climbs take five or six days and cost about 1300 dollars. Most of that is the Kilimanjaro entrance fee: 70 dollars per day of stay, 50 dollars per night of camping, a 20 dollar insurance fee for emergencies, and so on, for about 900 dollars in entrance fees. Even without climbing, the mountain lies on the route from Dar es Salaam through the Serengeti to Nairobi, the capital of Kenya, so it is easy to stop by.

To reach the Serengeti, travellers usually start from Arusha, a city in northern Tanzania. From there a local travel agency can take you on a five- or six-day visit to the Serengeti, and the Ngorongoro Crater east of the Serengeti is not to be missed either. Ngorongoro, which means "big hole" in the Maasai language, is the crater of an extinct volcano. It sits at 2300 meters above sea level and the crater is 18 km across. The surrounding terrain is high and rugged, so the animals there live in an environment cut off from the outside, and their density is high, which makes them easy to see.

Serengeti National Park sits on the northern border of Tanzania, and the area directly across the border is the Maasai Mara, a national park in Kenya. It is smaller than the Serengeti but shares the same ecosystem, so the animals you can see are similar. From July to September many animals migrate toward the Maasai Mara, so many travellers time their visit to that period. The Maasai Mara can be visited on a safari program that departs from Nairobi, the capital of Kenya.

Ethiopia, north of Kenya, is too far to reach from Kenya by land, so people usually fly. Flights for a trip to Africa often connect through Addis Ababa, the capital of Ethiopia, so Ethiopia can be visited on a stopover. Ethiopia also issues a visa on arrival for 50 dollars. Ethiopia is where the earliest human fossils were found, and Axum, an ancient kingdom of the region, and Gondar, the former capital of the Ethiopian Empire, are worth a visit. The Danakil Desert in northeastern Ethiopia is also a popular destination. It is famous as the place where you can get closest to an active volcano, and many people go there even though the region is dry and barren.

Africa has many other countries and many other places worth visiting besides the regions introduced here, but because of time limits the plan is to visit the countries above. Anyone who wants to join Brian on his journey through Africa this summer to meet a lion is welcome to get in touch.

The first line contains the number of countries to visit, $N$ ($1 \le N \le 8$).

Each of the next $N$ lines contains one country name, in the order of the visits. Each name is one of the following eight, and no name appears more than once: botswana, ethiopia, kenya, namibia, south-africa, tanzania, zambia, zimbabwe

Print the minimum total visa fee, in dollars, as an integer for a trip that visits the countries in the given order. All the information needed to solve the problem is what this problem states.