A higher resolution is required to access the IDE

- 35

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

Ticket to Ride is a classic board game by Alan Moon and Days of Wonder in which you earn points by connecting cities via train routes. In this puzzle, you must calculate the maximum possible score in a Ticket to Ride scenario.**EARNING POINTS**

- Each completed route provides a certain number of points.

- Each completed ticket card earns you a certain number of bonus points.

- Ticket cards that are not completed are worth negative points.

**COMPLETING ROUTES**

Each route connects two cities, and requires you to expend two resources, both

`trainCars`and cards, to complete it. The

`length`of the route informs you how many of each resource are required. A route of

`length`=

`trainCars`

**AND**3 cards.

**STARTING GAME STATE**

You will be provided with:

- Number of

`trainCars`available for use. (Resource #1)

- Number and type of cards in your hand (Resource #2)

- Number and nature of tickets in your hand.

- A list of available routes on the board, and the resources required to complete each one.

**SCORING ROUTES**

Points awarded for completing a route are based on the route

`length`:

- length of 1: 1 pt

- length of 2: 2 pts

- length of 3: 4 pts

- length of 4: 7 pts

- length of 6: 15 pts

**SCORING TICKETS**

Each ticket specifies two cities and a number of bonus points to be earned. If the two cities are connected via train routes (either directly or indirectly) then the points for the ticket are added to your score. If not, then the ticket’s points are deducted from your score.

**CARDS AND ROUTES**

Each

**card**in your hand is EITHER a colored card (

**route**is EITHER one of the

`length`cards

**of the SAME color**from your hand. So, to complete a

`length`=

**ENGINE CARDS**

Engines are wild, and can be used as a substitute for any colored card.

**GRAY ROUTES**

**MUST**be all of the same color (potentially supplemented with engines).

**FERRIES**

Some

**MUST**be engine cards.

**FERRY EXAMPLE**

A ferry of

`length`=

`requiredEngines`=

- 2 red cards and 1 engine,

- 1 black and 2 engines,

- but

**NOT**3 blue cards,

- and

**NOT**1 green, 1 yellow, and 1 engine

**SCORING EXAMPLE**

Given:

- A

- Two routes:

1) Athina to Smyrna (

`length`=

2) Smyrna to Angora (

`length`=

Total points received for completing both routes =

**11 POINTS**:

- 2 pts: complete route #1

- 4 pts: complete route #2

- 5 pts: complete ticket

Input

**Line 1:**Three space-separated integers: number of

`trainCars`, number of tickets (

`numTickets`) you have, and number of available routes (

`numRoutes`) on the board.

**Line 2:**Nine space-separated integers for the number of

`red`,

`yellow`,

`green`,

`blue`,

`white`,

`black`,

`orange`,

`pink`, and

`engine`cards you have in your hand.

**Next**One line for each ticket in your hand. Each line has an integer for the

`numTickets`lines:`points`value of the ticket, followed by two space-separated city names.

**Next**One line for each available route on the board. Each line has an integer for the

`numRoutes`lines:`length`of the route (in number of train cars), an integer for the number of

`requiredEngines`, a

`color`(

Output

A single integer indicating the maximum possible score.

Constraints

`trainCars`<

`numTickets`<

`numRoutes`<

Example

Input

6 1 3 1 2 0 0 0 0 3 0 0 6 Zurich Budapest 1 0 Red Wien Budapest 2 0 Yellow Zurich Munchen 3 0 Orange Munchen Wien

Output

13

A higher resolution is required to access the IDE