Milagros y Kimey visitan la panadería-ferretería de Sebastián para comprar algunos fusili-tornillos y churro-clavos, con el objetivo de reparar su bananamóvil, un vehículo completamente comestible que utilizarán para participar en la Carrera Ligera Tropical: una competencia donde todos los vehículos deben estar construidos exclusivamente con elementos comestibles.

El bananamóvil es un proyecto de ingeniería comestible complejo, y requiere fusili-tornillos de N tamaños distintos, en cantidades específicas. En particular, necesitan c[i] unidades del fusili-tornillo de tamaño i, para 1 ≤ i ≤ N.

Cada tamaño de fusili-tornillo tiene un precio por unidad de p[i]. Comprar todos los fusili-tornillos por separado podría resultar muy costoso.

Por suerte, Sebastián ofrece M promociones especiales. Cada promoción permite comprar un conjunto combinado de dos tipos de fusili-tornillos a un precio reducido. Específicamente, una promoción incluye a[j] unidades del fusili-tornillo de tamaño x[j] y b[j] unidades del tamaño y[j], a un precio total de d[j], el cual siempre es más barato que adquirir esos productos por separado.

Tu tarea es ayudar a Milagros y Kimey a encontrar la combinación de compras directas y promociones que logran el costo mínimo total que deben pagar para adquirir todos los fusili-tornillos necesarios para completar su bananamóvil, sin que les sobre ni un fusili-tornillo. (o sea, se debe comprar la cantidad exacta de cada fusili-tornillo)

Imaginate la lista de cantidades de productos sueltos que van a comprar Milagros y Kimey, concatenada con la lista de promociones que van a comprar (ambas en el órden dado en la entrada). Se debe encontrar la combinación que maximiza lexicográficamente esta lista.

=== Formato de entrada ===

N M
c[1] c[2] c[3] ... c[N]
p[1] p[2] p[3] ... p[N]
x[1] y[1] a[1] b[1] d[1]
x[2] y[2] a[2] b[2] d[2]
x[3] y[3] a[3] b[3] d[3]
...
x[M] y[M] a[M] b[M] d[M]


=== Formato de salida ===

Sean:

- C el costo total
- s[1], s[2], s[3], ..., s[N] la cantidad de cada producto suelto a comprar
- j[1], j[2], j[3], ..., j[M] la cantidad de cada promocion a comprar

La salida es la cadena

C:s[1],s[2],s[3],...,s[N]:j[1],j[2],j[3],...,j[M]

Se debe encontrar la solucion que maximiza lexicograficamente la lista de enteros s[1], s[2], ..., s[N], j[1], j[2], ..., j[M]

=== Ejemplo ===

Entrada:

2 2
2 2
10 10
1 2 2 1 10
1 2 1 2 10

Salida:

20:1,0:0,1

=== Datos de entrada ===

30 150
6 48 4 7 44 39 8 18 16 30 50 16 11 17 34 40 47 31 15 15 17 20 27 29 6 39 16 33 33 8
1 22 17 120 17 28 125 64 32 11 25 15 2 27 12 31 37 16 6 5 34 36 38 21 38 18 25 12 23 44
3 20 1 3 13
28 2 2 1 16
7 17 3 3 316
24 3 3 4 72
5 30 4 1 50
24 30 3 2 76
24 16 4 4 146
8 6 3 1 121
16 18 2 1 55
11 4 3 4 194
5 27 4 1 46
22 17 2 2 73
17 14 4 2 131
9 20 1 1 15
4 27 1 1 65
29 17 4 1 52
22 9 3 4 153
30 23 1 1 57
5 11 2 3 44
30 12 2 3 73
13 20 4 4 10
17 29 4 4 84
7 4 2 1 222
17 28 1 3 26
15 11 2 2 33
20 3 4 4 48
9 10 2 1 34
1 22 1 1 22
20 20 2 1 8
21 17 2 3 125
14 2 1 2 28
25 20 1 2 24
28 8 1 2 98
16 10 4 4 101
14 11 1 3 51
16 13 1 1 20
8 21 2 3 138
14 20 3 3 53
9 2 2 4 76
27 28 2 1 28
4 17 4 1 233
24 10 4 4 58
1 18 4 3 22
23 23 1 3 84
17 8 3 4 239
5 27 3 3 57
27 23 4 3 118
18 21 3 1 37
26 17 1 4 91
8 7 4 2 304
18 18 4 3 39
12 24 2 4 57
14 19 3 1 48
23 24 3 3 115
4 30 3 3 197
17 27 4 4 112
2 26 2 1 25
20 2 4 3 34
24 25 4 1 67
2 22 3 4 136
7 2 2 1 122
7 19 1 3 57
3 19 1 1 15
8 27 4 2 153
15 4 1 4 271
13 24 4 4 55
25 18 2 3 87
26 1 4 3 32
8 12 4 4 111
16 10 2 4 58
26 23 4 4 90
7 29 1 2 60
10 18 2 2 19
1 21 2 2 27
28 21 1 4 81
22 29 2 4 66
15 27 2 4 43
3 18 4 4 92
20 14 4 4 45
18 11 4 2 40
28 15 4 2 47
25 2 1 1 30
10 30 4 1 62
29 13 4 1 42
7 20 2 4 121
1 11 2 3 49
18 11 2 3 59
27 23 4 4 139
8 10 4 3 202
2 27 1 4 85
25 24 4 2 78
27 9 3 2 63
23 2 2 2 54
7 28 4 4 384
21 21 2 3 110
9 29 4 3 98
1 20 3 4 14
13 21 1 2 28
12 9 4 2 43
9 15 3 2 60
28 15 3 4 50
10 18 2 2 19
18 25 1 3 84
19 20 1 4 13
19 15 1 4 35
3 27 2 1 24
14 10 2 1 26
5 18 3 2 58
29 21 3 1 62
23 29 3 2 104
30 9 2 4 76
8 20 1 4 55
14 1 1 3 14
4 8 2 3 259
28 19 2 1 16
17 12 4 4 94
7 19 1 3 64
27 17 1 1 40
12 10 2 2 21
9 13 4 2 66
29 30 3 2 78
17 17 4 4 178
13 26 4 2 26
9 1 1 2 19
27 13 1 1 18
20 4 1 4 291
29 15 4 1 73
3 3 3 4 54
12 21 2 1 26
3 29 2 1 40
30 21 2 1 79
14 6 2 4 75
2 29 2 3 51
20 23 2 3 43
11 19 4 2 45
10 11 2 3 58
28 2 4 2 51
3 20 1 3 13
4 29 3 1 153
21 7 2 2 175
18 26 3 4 72
7 8 4 1 197
29 4 2 2 172
22 2 1 3 51
24 13 1 1 12
30 5 4 3 148
9 2 3 4 129
23 3 2 4 72
13 8 1 1 40
18 30 4 4 168