Under construction

Still being built. Things may change

Gasoline

Time limit2sMemory limit512 MB

Summary
Given station demands, refinery stocks, and allowed refinery-station pairs with travel times, find the minimum time to fully supply every station, or -1 if impossible.
Level

Hard8 of 10

Topics
Binary search, Graph, BFS, Greedy
Solved
No attempts yet

Problem

After the truckers' strike ended, you and the other logistics experts of Nlogônia now have the task of planning the resupply of the city's gas stations. To this end, information was collected about the stocks of R refineries and the demands of P gas stations. In addition, contractual restrictions prevent some refineries from serving some stations. When a refinery can supply a station, the minimum travel time to transport fuel from one place to the other is known.

The experts' task is to minimize the supply time for all stations while fully satisfying their demands. The refineries have a sufficiently large number of trucks, so it can be assumed that each truck will make at most one trip, from a refinery to a gas station. The capacity of each truck is larger than the demand of any station, but it may be necessary to use more than one refinery to meet a station's demand.

Your program must find the minimum time in which it is possible to fully supply all stations, respecting the refineries' stocks.

Input

The first line of the input contains three integers, P, R, and C, respectively the number of stations, the number of refineries, and the number of refinery-station pairs whose travel time will be given (1 ≤ P, R ≤ 1000 and 1 ≤ C ≤ 20000). The second line contains P integers Di (1 ≤ Di ≤ 10⁴), representing the demands, in liters of gasoline, of stations i = 1, 2, ..., P, in that order. The third line contains R integers Ei (1 ≤ Ei ≤ 10⁴), representing the stocks, in liters of gasoline, of refineries i = 1, 2, ..., R, in that order. Finally, the last C lines describe travel times, in minutes, between stations and refineries. Each of these lines contains three integers, I, J, and T (1 ≤ I ≤ P and 1 ≤ J ≤ R and 1 ≤ T ≤ 10⁶), where I is the identifier of a station, J is the identifier of a refinery, and T is the travel time of a truck from refinery J to station I. No pair (J, I) will be repeated. Not all pairs are given; if a pair is not given, contractual restrictions prevent the refinery from serving the station.

Output

Print an integer T indicating the minimum time in minutes for all stations to be completely supplied. If this is not possible, print -1.

Examples4

  1. Example 1

    Input
    3 2 5
20 10 10
30 20
1 1 2
2 1 1
2 2 3
3 1 4
3 2 5
    Expected output
    4

  2. Example 2

    Input
    3 2 5
20 10 10
25 30
1 1 3
2 1 1
2 2 4
3 1 2
3 2 5
    Expected output
    5

  3. Example 3

    Input
    4 3 9
10 10 10 20
10 15 30
1 1 1
1 2 1
2 1 3
2 2 2
3 1 10
3 2 10
4 1 1
4 2 2
4 3 30
    Expected output
    -1

  4. Example 4

    Input
    1 2 2
40
30 10
1 1 100
1 2 200
    Expected output
    200