#P3611. Minimum Weighted Perfect Fractional <i>b</i>-Matching

    ID: 2621 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>POJ Founder Monthly Contest – 2008.06.29, frkstyc

Minimum Weighted Perfect Fractional <i>b</i>-Matching

Description

In graph theory, a matching M of a graph G = (V,E) is defined as a pairwise disjoint subset of E. Put alternatively, a matching M of G is a subset of E such that each vertex covered by M is incident to exactly one edge in M. A perfect matching M of G is a matching that covers all vertices of G.

Extending the definition of a matching, the concept of b-matching is based on a graph G where each vertex v is associated with a non-negative integral balance b(v) and each edge e with a non-negative integral capacity u(e). A b-matching M of G is defined as an assignment of a non-negative integral bidirected flow x(e) ≤ u(e) to each edge e. A perfect b-matching is a b-matching where for each vertex v,

\sum_{e\in E(v)}x(e)=b(v),

in which E(v) denotes the set of all edges incident to v. Intuitively speaking, a perfect b-matching is a generalized perfect matching that allows each vertex to be incident to multiple edges and each edge to be used multiple times. A perfect fractional b-matching is a relaxation of a perfect b-matching. A perfect b-matching demands the integrality of the flows, whereas a perfect fractional b-matching permits that they take fractional values. Associating a weight c(e) with each edge e of G, the weight of a perfect fractional b-matching is defined as

\sum_{e\in E}c(e)x(e).

A minimum weighted perfect fractional b-matching is defined as the perfect fractional b-matching with the minimum weight.

Given a capacitated, weighted graph with a balance constraint on each vertex, find a minimum weighted perfect fractional b-matching. 

Input

The first line contains two integers m and n, (1 ≤ m ≤ 1000, 1 ≤ n ≤ 100), the numbers of edges and vertices of the graph. The vertices are numbered 1 through n.

The next m lines each contain four integers x, y, u(e) and c(e) (1 ≤ x, yn, 1 ≤ u(e) ≤ 200, 1 ≤ c(e) ≤ 200) describing an edge e, where x and y are the endpoints of e, and u(e) and c(e) are the capacity and the weight of e, respectively.

The last n lines each contain an integer b(vi) (1 ≤ b(vi) ≤ 200), the balance of vertex i.

Output

Output the weight of the found matching.

4 3
3 1 6 4
3 1 10 4
2 3 2 2
2 1 6 6
2
2
4
12

Source

POJ Founder Monthly Contest – 2008.06.29, frkstyc