Last Orders

You are attempting a legendary pub crawl across town.

The town has  junctions which are connected by  roads. There is a pub at each 
junction. Each road could be traveled in both directions and has a non-negative 
travel time. There could be multiple roads between the same pair of junctions. 
You start the pub crawl at time  in pub .

Pub  is located at junction  and will close at absolute time
. A pint must be finished at or before closing time in order to count.

Your drinking ability changes as the night goes on:
  The 1st pint takes  time units,
	The 2nd takes , and so on, with the -th pint taking .
Please note that  are not necessarily increasing.

You may visit pubs in any order (not necessarily starting by drinking at pub )
and may return to the same pub multiple times, but you cannot drink two
consecutive pints in the same pub.

Your task is to maximize the number of pints consumed before closing times run
out.

Input
    itemize
        One line containing the number of pints you are capable of drinking,  ().
        One line containing  integers: the number of seconds taken to drink the pints,  ().
        One line containing the number of pubs,  ().
        One line containing  integers, the integer closing times  of the pubs in seconds ().
        One line containing the number of roads,  ().
         further lines, each containing three integers: , , and
            , indicating that there is a connection between pubs  and  taking
             seconds to travel (; ). Please note that there could be more than one road between same pair of pubs.
    itemize

Output
    Output an integer - the maximum number of pints you can drink before all of
    the pubs are closed.