Untitled

Tuần Trăng Mật
Tuần trăng mật

Đám cưới anh Uranus diễn ra rất vui vẻ, chỉ có Tomoky là có chút hậm hực. Sau đám cưới, anh Uranus muốn đi tuần trăng mật ở thành phố Đà Lạt xinh đẹp.

Thành phố Đà Lạt gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m (m <= n*(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1,2,…m) cho phép đi từ địa điểm u_j tới địa điểm v_j với chi phí đi lại là số nguyên dương c(u_j, v_j).

Anh Uranus muốn xuất phát từ điểm du lịch 1 và đi thăm k địa điểm du lịch s_1, s_2, …, s_k (khác địa điểm 1) và sau đó quay về địa điểm xuất phát 1 với tổng chi phí là nhỏ nhất.

Cho thông tin về hệ thống giao thông và k địa điểm du lịch s_1, s_2, …, s_k. Hãy giúp anh Uranus xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm s_1, s_2, …, s_k sau đó quay về địa điểm du lịch 1 với tổng chi phí nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên dương T là số bộ test. Mỗi bộ test gồm:

• Dòng thứ nhất chứa 3 số nguyên n, m, k (n <= 1000 và k <= 15).

• Dòng thứ hai chứa k số nguyên dương s_1, s_2, …, s_k.

• Dòng thứ j trong m dòng tiếp theo chứa 3 số nguyên dương u_j, v_j, c(u_j, v_j) cho biết thông tiên về tuyến đường thứ j. Biết rằng u_j luôn khác v_j, và c(u_j, v_j) <= 10^9.

Output

In ra một số nguyên là tổng chi phí nhỏ nhất tìm được. Nếu không tìm được một hành trình du lịch nào, in ra số -1.

Example

Input:

1

6 8 2

2 5

1 2 4

2 4 2

4 3 3

3 1 4

4 1 5

3 5 5

5 3 1

5 6 7

 Output:

Case #1

19



Case #2

57

/////////////////////////////////////
lịch trình quảng cáo
Một cửa hàng cần hiển thị quảng cáo 3 lần một ngày.

Tuy nhiên, họ chỉ có 1 bảng điện để hiển thị quảng cáo nên nên chọn thời điểm hiển thị quảng cáo sao cho khách xem được nhiều nhất có thể.

 

Khi khách xem quảng cáo, họ có thể nhận được số điểm được tính như sau:

1. Ba Quảng cáo  có độ dài L1, L2, L3 và số điểm mà một người có thể nhận được sau khi xem chúng là P1, P2, P3.

2. Khách truy cập chỉ có thể nhận được điểm của Quảng cáo  khi họ xem  hết Quảng cáo đó (từ đầu đến cuối Quảng cáo đó)

3. Khi một khách truy cập xem nhiều Quảng cáo  và đồng thời nhận được điểm cho họ, thì chỉ những Quảng cáo  có điểm cao nhất mới được trao cho người đó.

  4. Mỗi lần chỉ được hiển thị một Quảng cáo trên bảng điện (Nhưng Quảng cáo tiếp theo   có thể hiển thị ngay sau khi Quảng cáo trước đó kết thúc)

 

Cho biết độ dài của mỗi Quảng cáo L1, L2, L3 và số điểm đạt được cho chúng P1, P2, P3, thời gian đến của mỗi khách vào cửa hàng và thời gian họ ở lại cửa hàng, hãy viết chương trình để chọn thời gian hiển thị quảng cáo sao cho càng nhiều điểm càng tốt cho khách truy cập. In ra tổng số điểm mà khách truy cập có thể nhận được.

 

Ví dụ : Có 7 khách vào quán với thời gian đến và ở như sau

 

Khách 1

Khách 2

Khách 3

Khách 4

Khách 5

Khách 6

Khách 7

Thời gian đến

2

6

3

7

1

2

1

Khoảng thời gian

2

4

3

2

1

1

10

 

 

Chiều dài

điểm

quảng cáo 1

1

1

quảng cáo 2

2

2

quảng cáo 3

3

3

 

Giả sử rằng Quảng cáo 1 được hiển thị ở thời điểm 2, Quảng cáo 2 ở thời điểm 7 và Quảng cáo 3 ở thời điểm 3, khách truy cập sẽ xem quảng cáo theo lịch trình bên dưới:

 

Khách 1

Khách 2

Khách 3

Khách 4

Khách 5

Khách 6

Khách 7

Quảng cáo 1

Đồng hồ

-

-

-

-

Đồng hồ

Đồng hồ

Quảng cáo 2

-

Đồng hồ

-

Đồng hồ

-

-

Đồng hồ

Quảng cáo 3

-

-

Đồng hồ

-

-

-

Đồng hồ

(Lưu ý rằng khách truy cập 1 đã không xem hết Ads3, vì vậy điểm của Ads3 không được trao cho anh ta)

 

Số điểm mà mỗi khách truy cập có thể nhận được khi xem Quảng cáo được hiển thị như sau:

 

Khách 1

Khách 2

Khách 3

Khách 4

Khách 5

Khách 6

Khách 7

Quảng cáo 1

1

-

-

-

-

1

1

Quảng cáo 2

-

2

-

2

-

-

2

Quảng cáo 3

-

-

3

-

-

-

3

Tổng cộng 12 Điểm

1

2

3

2

0

1

3

(Khách 7 đã xem đầy đủ tất cả các Quảng cáo, tuy nhiên anh ta chỉ có thể nhận được điểm cao nhất của một Quảng cáo - tức là 3 điểm của Quảng cáo 3)




Có nhiều cách để sắp xếp thời gian hiển thị và phương pháp trên cho chúng ta tổng số điểm tối đa mà khách truy cập có thể nhận được, vì vậy câu trả lời trong trường hợp này là 12.

 

[ Ràng buộc ]

- Số lượng khách N (1 ≤ N ≤ 50)

- Thời gian đến Ai, khoảng thời gian Di của mỗi khách và độ dài của mỗi Quảng cáo L1, L2, L3 được cho dưới dạng số nguyên (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)

- Ái + Dị ≤ 50

- L1 + L2 + L3 ≤ 50

- Thời gian bắt đầu của một Quảng cáo : 1 ≤ thời gian bắt đầu ≤ 50

- P1, P2, P4 là các số nguyên (1 ≤ P1, P2, P3 ≤ 1000)

 

[ Đầu vào ]

Dòng 1 ghi T - tổng số TC (T ≤ 50)

Trong mỗi TC:

 - Dòng thứ nhất ghi N, L1, L2, L3, P1, P2, P3 theo thứ tự

 - N dòng tiếp theo: mỗi dòng ghi thời gian đến Ai và thời gian Di của từng khách

5                          // Số test T=5

7 1 2 3 1 2 3          // Test case 1 N=7, L1=1, L2=2, L3=3, P1=1, P2=2, P3=3

2 2                        // A1 = 2, D1 = 2

6 4                        //...

3 3

7 2

1 1

2 1

1 10

4 3 2 1 6 4 3

1 5

1 3

2 4

2 2

...

 

[ Đầu ra ]

Out đưa ra tổng số điểm tối đa mà khách truy cập có thể nhận được khi xem quảng cáo.

Trường hợp 1

12

Trường hợp #2

18

Trường hợp #3

17

Trường hợp #4

16

Trường hợp #5

17998