An earthquake with a magnitude of 8.0 on the Richter scale has just occurred in Seismicity. Houses collapsed, many people are homeless and food becomes scarce. Now, it is time for the rest of the country to help. The country has N cities, numbered from 1 to N, being the city N Seismicity. Each city has a maximum number of tons of basic goods (water, food, blankets, clothing, medicine) it can donate, and these basic goods will be transported to Seismicity in truck containers through the national road network. Each road is bidirectional and connects two cities. Additionally, if government decides to use a road to move trucks along it, it must pay a compensation to the road neighbors because of contamination and noise, and no more than a fixed number of tons can be transported over it. Your task is to compute the maximum number of tons of basic goods that can be taken from other cities to Seismicity and the minimum amount of money to be paid to road neighbors to achieve it. Input The input consists of several test cases. The first line of each test case contains two blank-separated integers N and M, where N is the number of cities (2 ≤ N ≤ 20), and M is the number of roads (1 ≤ M ≤ 500). Then N − 1 lines follow, each one containing an integer ti indicating the maximum numberoftonsofbasicgoodsthatthecityicandonate(0≤ti ≤50,foreach1≤i≤N−1). Each of the next M lines contains four blank-separated integers a, b, w and c, indicating that there is a road between cities a and b over which no more than w tons can be transported at a cost of c per ton (1≤a<b≤N,1≤w≤50,1≤c≤50). Notethatallroadsarebidirectional,andthattheremaybe several roads between any two fixed cities. Output For each test case, print the maximum number of tons of basic goods that can be taken from other cities to Seismicity, followed by the minimum amount of money to be paid to road neighbors to achieve it. Sample Input 21 8 1232 23 8 1232 1224 1223 23 8 1252 1244 1243 31 4 5
2/2 1232 44 10 15 8 1 2 10 5 1 4 10 8 2 4 30 10 3464 Sample Output 36 7 20 8 19 00 31 254