Aurevia, Brelosia, Cyrenia and Zerathania are four countries with their currencies being Aurels, Brins, Crowns, and Zentars, respectively. The currencies have different exchange values. Crown's currency exchange rate with Zentars = 0.5, i.e., 1 Crown is worth 0.5 Zentars.

Three travelers, Jano, Kira, and Lian set out from Zerathania visiting exactly two of the countries. Each country is visited by exactly two travelers. Each traveler has a unique Flight Cost, which represents the total cost of airfare in traveling to both the countries and back to Zerathania. The Flight Cost of Jano was 4000 Zentars, while that of the other two travelers were 5000 and 6000 Zentars, not necessarily in that order. When visiting a country, a traveler spent either 1000, 2000 or 3000 in the country's local currency. Each traveler had different spends (in the country's local currency) in the two countries he/she visited. Across all the visits, there were exactly two spends of 1000 and exactly one spend of 3000 (in the country's local currency).

The total “Travel Cost” for a traveler is the sum of his/her Flight Cost and the money spent in the countries visited.

The citizens of the four countries with knowledge of these travels made a few observations, with spends measured in their respective local currencies:

i. Aurevia citizen: Jano and Kira visited our country, and their Travel Costs were 3500 and 8000, respectively.

ii. Brelosia citizen: Kira and Lian visited our country, spending 2000 and 3000, respectively. Kira's Travel Cost was 4000.

iii. Cyrenia citizen: Lian visited our country and her Travel Cost was 36000.

What is the sum of Travel Costs for all travelers in Zentars?

The correct answer is 41000.

To solve this, we need to carefully deduce the visits, spending amounts, flight costs, and currency exchange rates for each traveler.

1. Determining the Countries Visited
There are exactly 6 visits in total (3 travelers visiting 2 countries each). The observations tell us:
- Jano and Kira visited Aurevia.
- Kira and Lian visited Brelosia.
- Lian visited Cyrenia.
Since each traveler visits exactly two countries, and each country is visited exactly twice, Jano must have also visited Cyrenia. Thus, the visits are:
- Jano: Aurevia and Cyrenia
- Kira: Aurevia and Brelosia
- Lian: Brelosia and Cyrenia

2. Distributing the Spending Amounts
Across all 6 visits, the spending amounts (in local currencies) are exactly two 1000s, three 2000s, and one 3000. Each traveler must have two different spending amounts for the two countries they visit.
From the Brelosia citizen, Kira spent 2000 and Lian spent 3000 in Brelosia. This accounts for the only 3000 spend.
Since Kira spent 2000 in Brelosia, and her other spend must be different, she must have spent 1000 in Aurevia (because if she spent 3000 it would violate the total count, and she cannot repeat 2000).
Jano needs two different spending amounts from the remaining pool (one 1000 and two 2000s). Jano's spends must therefore be 1000 and 2000. This leaves exactly one 2000 spend for Lian's visit to Cyrenia.
To summarize the spends in local currencies:
- Kira: 1000 in Aurevia, 2000 in Brelosia
- Lian: 3000 in Brelosia, 2000 in Cyrenia
- Jano: 1000 and 2000 in Aurevia and Cyrenia (order to be determined)

3. Establishing Exchange Rates and Jano's Flight Cost
Let $R_A$, $R_B$, and $R_C$ be the exchange rates converting 1 unit of the local currency to Zentars. We are given that 1 Crown = 0.5 Zentars, so $R_C=0.5$.
A traveler's Total Travel Cost in Zentars is their Flight Cost plus the Zentars equivalent of their local spends.

For Jano, the Flight Cost is 4000 Zentars. The Aurevia citizen observed Jano's Total Cost to be 3500 Aurels. Converting this to Zentars gives:

$4000+({\mathrm{Spend}}_A\times R_A)+({\mathrm{Spend}}_C\times 0.5)=3500\times R_A$

Rearranging this equation, we get:

$4000+({\mathrm{Spend}}_C\times 0.5)=(3500-{\mathrm{Spend}}_A)\times R_A$

We test the two possible spending scenarios for Jano:
Case 1: Spend 1000 in Aurevia and 2000 in Cyrenia.
This gives $4000+1000=2500\times R_A$, which means $R_A=2$.
Case 2: Spend 2000 in Aurevia and 1000 in Cyrenia.
This gives $4000+500=1500\times R_A$, which means $R_A=3$.

4. Deducing Kira's Flight Cost and Validating the Cases
Kira's Total Travel Cost is reported as 8000 Aurels by the Aurevia citizen, and 4000 Brins by the Brelosia citizen. Converting these to Zentars, we have two expressions for Kira's Total Cost:

${\mathrm{Flight}}_K+(1000\times R_A)+(2000\times R_B)=8000\times R_A$

${\mathrm{Flight}}_K+(1000\times R_A)+(2000\times R_B)=4000\times R_B$

From the second equation, we can simplify to find the 2000 Brins equivalent in Zentars:

$2000\times R_B={\mathrm{Flight}}_K+(1000\times R_A)$

Substitute this into the first equation:

${\mathrm{Flight}}_K+{\mathrm{Flight}}_K+(1000\times R_A)=7000\times R_A$

$2\times {\mathrm{Flight}}_K=6000\times R_A$

${\mathrm{Flight}}_K=3000\times R_A$

We know the remaining flight costs are 5000 and 6000 Zentars. If we apply Case 2 where $R_A=3$, Kira's flight cost would be 9000 Zentars, which is impossible. Thus, Case 1 must be correct, meaning $R_A=2$.
This perfectly matches Kira's flight cost to 6000 Zentars. By elimination, Lian's flight cost is the remaining 5000 Zentars.

5. Finding the Remaining Exchange Rate and Verifying
Using Kira's flight cost (6000) and $R_A=2$ in our simplified equation:

$2000\times R_B=6000+(1000\times 2)=8000$

This gives $R_B=4$. We can verify this setup entirely using Lian's Total Cost. Lian's cost in Zentars is her flight (5000) plus 3000 Brins (3000 × 4 = 12000) and 2000 Crowns (2000 × 0.5 = 1000):

$5000+12000+1000=18000$

The Cyrenia citizen reported Lian's cost as 36000 Crowns. Since 1 Crown = 0.5 Zentars, 36000 × 0.5 = 18000 Zentars, which is a perfect match!

6. Calculating the Final Sum
Now we calculate the total Travel Costs in Zentars for all travelers:
- Jano's Travel Cost = 3500 Aurels × 2 = 7000 Zentars.
- Kira's Travel Cost = 8000 Aurels × 2 = 16000 Zentars.
- Lian's Travel Cost = 18000 Zentars.

Summing these up to find the final requested value:

$7000+16000+18000=41000$

The total sum of Travel Costs for all travelers in Zentars is exactly 41000.