In Berland a new movie was released on the occassion of 14th Feb. The craze for this movie was very much among the peoples of the city. So many of them decided to go to the only Movie Theatre of Berland. As berland is very much developed there are many large(tall) buildings, including the movie theatre. At each building except theatre, there exist a person (who wants to see movie) or a taxi driver with his taxi. As it is very late in the night each taxi driver will only accomodate only one passenger and also he will only drive for T[i] HRS (return journey is not included). You will be given the distance between building D[i] and the speed of each taxi driver S[i]. As I am the owner of this theatre help me by telling, the maximum number of people I will see in the theatre for the movie. N+P+1th building is the my theatre. Also, if a taxi starts his journey by taking a passenger, it only stops at the theatre.

Input

• First line contains TT the number of test cases.
• First line of each test test case contains N, P and R denoting the number of taxi, number of people, and the number of roads between buildings.
• Next line contains N space-seperated integers representing the building where taxi is present.
• Next line contains P space-seperated integers representing the building where passengers is present.
• Next R lines contains X, Y, and D[i] the building connected via road and the distance between them in KMs.
• Next line contains N space-sperated integers S[i] giving the speed details of each taxi in KM/HRs.
• Next line contains N space-sperated integers T[i] giving the time details of each taxi in HRs.

Output

• Maximum number of people that will visit my theatre.

Constraints 

• 1 <= TT <= 5
• 1 <= N <= 500
• 1 <= P <= 1000
• 1 <= R <= 50000
• 1 <= X, Y <= N
• 5 <= S[i] <= 50
• 1 <= T[i] <= 5
• 1 <= D[i] <= 100

Example

Input:
1
1 2 4
2
1 3
1 2 5
2 3 5
3 4 10
1 3 8
20
1

Output:
1