Stepan is a very experienced olympiad participant. He has n cups for Physics olympiads and m cups for Informatics olympiads. Each cup is characterized by two parameters — its significance c i and width w i . Stepan decided to expose some of his cups on a shelf with width d in such a way, that: there is at least one Physics cup and at least one Informatics cup on the shelf, the total width of the exposed cups does not exceed d , from each subjects (Physics and Informatics) some of the most significant cups are exposed (i. e. if a cup for some subject with significance x is exposed, then all the cups for this subject with significance greater than x must be exposed too). Your task is to determine the maximum possible total significance, which Stepan can get when he exposes cups on the shelf with width d , considering all the rules described above. The total significance is the sum of significances of all the exposed cups. The first line contains three integers n , m and d ( 1 ≤ n , m ≤ 100 000 , 1 ≤ d ≤ 10 9 ) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf. Each of the following n lines contains two integers c i and w i ( 1 ≤ c i , w i ≤ 10 9 ) — significance and width of the i -th cup for Physics olympiads. Each of the following m lines contains two integers c j and w j ( 1 ≤ c j , w j ≤ 10 9 ) — significance and width of the j -th cup for Informatics olympiads. Print the maximum possible total significance, which Stepan can get exposing cups on the shelf with width d , considering all the rules described in the statement. If there is no way to expose cups on the shelf, then print 0 . In the first example Stepan has only one Informatics cup which must be exposed on the shelf. Its significance equals 3 and width equals 2 , so after Stepan exposes it, the width of free space on the shelf becomes equal to 6 . Also, Stepan must expose the second Physics cup (which has width 5 ), because it is