Background

If time could go back to the past, perhaps everything would be nothing...

Little W takes a time machine to a four-dimensional spacetime, and begins his treasure-hunting journey there.

Problem Description

The entire four-dimensional spacetime can be seen as a four-dimensional grid graph. Little W starts at $(1,1,1,1)$, and the exit is at $(m,m,m,m)$. However, since Little W is a visitor to this spacetime, his movement is restricted in some ways. Each time, he can only increase one of the four coordinates by $1$. That is, each step he can only move one step to the right, upward, forward, or * (the weak/problemsetter could not think of how to describe it).

There are $n$ treasures in this spacetime. The coordinates of the $i$-th treasure are $(a_i,b_i,c_i,d_i)$, and its value is $v_i$.

Little W wants to know the maximum total value of treasures he can take. Since Little W also likes to plan ahead, he also hopes to find multiple different plans that can all achieve the maximum total value. This number may be very large, so output it modulo $998244353$.

Note: Two plans are different if and only if there is at least one treasure choice that is different between them (multiple treasures at the same position count as only one plan). If only the route is different but the final chosen treasures are the same, then they are not considered different plans.

(Be careful: two treasures may be at the same position.)

Input Format

The first line contains two integers $n,m$, representing the number of treasures and the maximum grid coordinate value.

The next $n$ lines each contain $5$ integers, which are $a_i,b_i,c_i,d_i,v_i$.

Output Format

Output two lines. The first line is the maximum total value. The second line is the number of plans that satisfy the requirement, modulo $998244353$.

5 5
1 1 1 1 5
2 2 2 2 4
1 1 2 2 3
3 1 3 1 10
5 5 5 5 1

16
1

20 1000000000
20204201 39958379 15138434 34289618 398078390
85600475 39563639 66410111 36702766 611878653
36702694 1628762 125746709 79172847 611878653
103077330 79188107 6711555 56295346 611878653
212677316 202221253 26717633 234187985 158044893
297040787 198938585 43827694 296390944 158044893
109256220 180224853 267561686 65767679 472347047
167183048 72650618 4390517 30073538 471045792
214834767 93996707 94416376 34549122 359059039
89445418 135311221 266840392 213735818 398078390
343357648 61588748 188180842 396968607 144378900
285457193 157755350 336368020 572049737 472347047
171728638 398663231 323772972 359470762 611878653
234684711 226541116 270561472 376433946 229386389
293174669 58119648 352134416 262971247 144378900
182250938 623413311 303663331 506122949 611878653
817319765 321076346 200801449 745136845 698518241
26356940 295529493 725103952 845588002 533478406
510252473 498314898 168621119 519205227 472347047
947274653 288133984 692904616 340022215 611878653

1696104353
6

Hint

For Sample 1, the best way is to move from $(1,1,1,1)$ slowly to $(3,1,3,1)$, and then slowly to $(5,5,5,5)$, obtaining a value of $16$. There is only $1$ best path.

For all testdata, $1\le a_i,b_i,c_i,d_i\le m$, $1\le v_i\le 10^9$。

Translated by ChatGPT 5