Covered Vertex Sets by Matchings in Bipartite Graphs

Consider a bipartite graph in which the vertices are partitioned into two disjoint sets \(A\) and \(B\). Each edge connects one vertex in \(A\) with one vertex in \(B\). A matching is a set of edges such that no two edges share a common endpoint. We say that a matching \(M\) covers a set of vertices \(V\) if every vertex in \(V\) is incident to at least one edge in \(M\>.

Each vertex in the graph is assigned a positive integer weight. The weight of a vertex set \(V\) is defined as the sum of the weights of the vertices in \(V\).

Given a parameter \(t\), your task is to count the number of vertex subsets \(V\) such that the total weight of \(V\) is at least \(t\) and there exists at least one matching \(M\) that covers \(V\) (i.e. every vertex in \(V\) is an endpoint of some edge in \(M\)).

Note that an edge in a matching can cover both of its endpoints simultaneously.

Input Format: The graph is given in a structured format as described below.

inputFormat

The first line contains four integers: n1, n2, m, and t, where n1 is the number of vertices in set \(A\), n2 is the number of vertices in set \(B\), m is the number of edges, and t is the target weight.

The second line contains n1 positive integers representing the weights of the vertices in \(A\) (indexed from 1 to n1).

The third line contains n2 positive integers representing the weights of the vertices in \(B\) (indexed from 1 to n2).

Each of the following m lines contains two integers a and b (1-indexed) which indicate that there is an edge connecting the a-th vertex of \(A\) and the b-th vertex of \(B\).

outputFormat

Output a single integer — the number of vertex subsets \(V\) (possibly non‐contiguous) that satisfy both conditions: (1) the total weight of \(V\) is at least \(t\), and (2) there exists at least one matching \(M\) in the graph that covers \(V\).

sample

2 2 2 3
1 2
2 1
1 1
2 2

10