Problem A
Fancy Antiques
You are hosting a fancy party for fancy friends. And, like any fancy party, you need to buy some fancy antiques to put up around the venue (your house).
There is a set of
It turns out that even though you can tell the difference,
most people cannot tell the original version from the knock-off
version of any given antique. And, because the shops can get
away with it, sometimes the knock-off is more expensive than
the original! Since the party is tomorrow, you only have time
to visit
Suppose that there are three shops, and three antiques we would like to buy.
-
Antique
sells for at shop . Its knockoff sells for at shop . -
Antique
sells for at shop . Its knockoff sells for at shop . -
Antique
sells for at shop . Its knockoff sells for at shop .
Suppose you only have time to go to two shops. You can go to
shops
If you only have time to visit one shop, then it is impossible. You cannot buy a version of all three items by visiting a single shop.
Given the costs of the antiques/knock-offs at the shops, what is the minimum total cost to buy one version of each antique?
Input
Each input will consist of a single test case. Note that
your program may be run multiple times on different inputs. The
first line of input will consist of three space-separated
integers:
-
is the index of the shop that sells the original version of the antique ( ) -
is the price of the original version of the antique at shop ( ) -
is the index of the shop that sells the knock-off version of the antique ( ) -
is the price of the knock-off version of the antique at shop ( )
Output
If it is possible to collect all of the antiques while
visiting no more than
Sample Input 1 | Sample Output 1 |
---|---|
3 3 2 1 30 2 50 2 70 3 10 3 20 1 80 |
60 |
Sample Input 2 | Sample Output 2 |
---|---|
3 3 1 1 30 2 50 2 70 3 10 3 20 1 80 |
-1 |