Treasure Hunt in a 4D Grid

In a 4-dimensional space, we can view the entire spacetime as a 4D grid. Initially, Little W is at ( (1,1,1,1) ) and the exit is at ( (m,m,m,m) ). However, due to restrictions in this foreign spacetime, at each move Little W may only increase exactly one of his four coordinates by 1. In other words, each move corresponds to a step in one of the four directions.

There are ( n ) treasures hidden in this grid. The ( i\text{th} ) treasure is located at ( (a_i,b_i,c_i,d_i) ) and has a value of ( v_i ). Note that several treasures might be located at the same cell; if so, visiting that cell collects all treasures there but counts as a single choice in terms of distinct solution schemes.

Little W wants to know the maximum total treasure value he can collect along some monotonic path from ( (1,1,1,1) ) to ( (m,m,m,m) ) that only moves by increasing one coordinate at a time. Moreover, he wants to know in how many different ways (i.e. by selecting different sets of treasure locations) this maximum value can be achieved. Two solutions are considered different if and only if the set of treasure cells chosen differs (note that if a cell contains multiple treasures, picking that cell is counted as one decision). Since the number of ways can be large, output it modulo ( 998244353 ).

A cell ( (a, b, c, d) ) can be reached from ( (1,1,1,1) ) if and only if (1\le a,b,c,d\le m) and the moves are done by incrementing exactly one coordinate at a time, ensuring that for any two visited treasure cells ( p=(a_1,b_1,c_1,d_1) ) and ( q=(a_2,b_2,c_2,d_2) ) with ( p ) coming before ( q ), it holds that ( a_1\le a_2,\ b_1\le b_2,\ c_1\le c_2,) and ( d_1\le d_2 ).

inputFormat

The first line contains two integers ( m ) and ( n ) -- the dimension parameter and the number of treasures. Each of the next ( n ) lines contains five integers: ( a_i\ b_i\ c_i\ d_i\ v_i ), representing the coordinates of a treasure and its value.

outputFormat

Output two integers separated by a space: the maximum total value that Little W can collect and the number of distinct ways to achieve this maximum (modulo ( 998244353 )).

sample

2 3
1 1 1 1 5
1 1 1 2 10
1 1 2 2 7

22 1