Bob's English class has been given a project which must be done in pairs. The class size, , is even. Each pair needs to meet outside class to do the project.

The city which Bob and his classmates live in is a tree. It has zones labelled . There are roads so that one can travel from any zone to any other. The road connects zones and and has distance .

The student lives in zone . Bob defines the **cost** of a pair to be the distance between the zones of the two students in the pair. Bob is wondering what the total of the costs is. Since the pairs haven't been assigned yet, he wants to know the worst-case. That is, what is the maximum possible total of the costs?

#### Constraints

is even

##### Subtask 1 [10%]

for all

##### Subtask 2 [20%]

##### Subtask 3 [30%]

##### Subtask 4 [40%]

#### Input Specification

The first line contains two space-separated integers, and .

The next line contains space-separated integers, .

The next lines each contain three space-separated integers, , the description of road.

#### Output Specification

Output a single integer, the maximum possible total.

#### Sample Input 1

```
8 4
2 2 2 2 1 2 2 2
1 2 7
1 3 3
1 4 1
```

#### Sample Output 1

`7`

#### Explanation for Sample 1

The pairs of students give costs . The total is which is the maximum possible.

#### Sample Input 2

```
8 8
1 2 3 4 5 6 7 8
1 4 2
2 4 7
3 4 7
4 5 1
5 6 2
6 7 3
7 8 4
```

#### Sample Output 2

`36`

#### Explanation for Sample 2

The pairs of students give costs . The total is which is the maximum possible.

#### Sample Input 3

```
10 5
1 1 1 1 1 5 5 5 5 5
1 2 1
2 3 1
3 4 1
4 5 1
```

#### Sample Output 3

`20`

#### Explanation for Sample 3

The pairs of students give costs . The total is which is the maximum possible.

## Comments