shunfurh 于 2017.08.31 09:14 提问

The Best Travel Design

Dou Nai is an excellent ACM programmer, and he felt so tired recently that he wants to release himself from the hard work. He plans a travel to Xin Jiang. With the influence of literature, he wishes to visit Tian Chi, Da Ban Town, Lou Lan mysterious town, Yi Li, and other sights that also have great attraction to him. But the summer vocation time is not long. He must come back before the end of the summer vocation. For visiting more sights and all the necessary sights, he should make a thorough plan. Unfortunately, he is too tired to move, so you must help him to make this plan. Here are some prerequisites: there are two ways of transportation, bus and train, and velocity of the bus is 120km/h and the train is 80km/h.Suppose the travel is started from Urumuqi (point 1), and the end of the travel route is Urumuqi too. You need to spend some time to visit the sights, but the time of each visit is not always equal. Suppose we spend 12 hours on traveling every day.

Input

There are several test cases. For each case, the first line is three integers N, M and K. N (1<=n<=15) is the number of sights, M(0<=M<=N) is total sights he must arrived(sight 1 is always must be arrived) and K is total traveling time( per day). The second line is M integers which sights he must arrived. The third line is N integers, the ith integer means the time he will stay in the sight i (per hour). Then several lines follow. Each line is four integers x,y,len��and��kind��1<=x,y<=n,0<len<=1000, means there is a bidirectional path between sights x and y,the distance is len, kind=0 means x and y are connected by train, kind=1 is by bus.

x=y=len=kind=0 means end of the path explaination.

N=M=K=0 means end of the input.

Output

For each case, output maximum sights he will travel with all necessary sights visited or "No Solution" if he can't travel all the sights he like best in time.

Sample Input

3 3 3
1 2 3
10 8 6
1 2 120 0
1 3 60 1
2 3 50 1
0 0 0 0
3 3 2
1 2 3
10 8 6
1 2 120 0
1 3 60 1
2 3 50 1
0 0 0 0
0 0 0

Sample Output

3
No Solution

2个回答

caozhy      2017.09.15 00:19

huang931027   2017.08.31 11:10

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
ACM

shunfurh 回复Luffy_fans_zh: I wanna fuck your mother
5 个月之前 回复
huang931027 回复shunfurh: 放你妈的屁话，你都可以jb发，老子是把NM 草了还是咋得，你管老子说不说废话。真你吗SB．
6 个月之前 回复
shunfurh 不会不要瞎jb废话
6 个月之前 回复