#P4849. 寻找宝藏

寻找宝藏

题目背景

如果时光回到从前,或许,一切只是虚无……

小 W 坐着时光穿梭机到达了一个四维时空,在这里,开始了他的寻宝之旅。

题目描述

整个四维时空可以看做是一个四维的网格图,小 W 在 (1,1,1,1)(1,1,1,1) 这个位置,出口在 (m,m,m,m)(m,m,m,m)。但由于小 W 毕竟是外来时空的人,他的行动在这里受到了一些限制。每次他只能使四个坐标中的一个加上 11。也就是说,他每次只能向右,向上,向前和向*(蒟蒻的出题人想不出来怎么形容了)走一步。

这个时空中有 nn 个宝藏,第 ii 个宝藏的坐标是 (ai,bi,ci,di)(a_i,b_i,c_i,d_i),价值为 viv_i

小 W 想知道,他能够拿走宝藏的最大价值和是多少。由于小 W 也是一个喜欢未雨绸缪的人,他也希望能够找到多种不同的方案使它们都可以达到最大价值和的要求。不过这个数有可能很大,输出它对 998244353998244353 取模的结果即可。

注意!两个方案不同当且仅当两个方案中至少有一个宝藏选择的不同,如果仅仅路线不同而最终都选择了相同的宝藏不算不同的方案。

(小心两个宝藏待在相同的位置哦……)

输入格式

第一行两个数 n,mn,m,分别代表宝藏个数和网格坐标的最大值。

接下来 nn 行,每行 55 个数,分别是 ai,bi,ci,di,via_i,b_i,c_i,d_i,v_i

输出格式

输出两行,第一行是最大价值和,第二行是满足条件的方案个数对 998244353998244353 取模的结果。

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

提示

对于样例 1,最好的办法是 (1,1,1,1)(1,1,1,1) 慢慢走到 (3,1,3,1)(3,1,3,1),再慢慢走到 (5,5,5,5)(5,5,5,5),获得 1616 的价值。最好的路径只有这 11 条。

Luogu

对于所有数据,1ai,bi,ci,dim1\le a_i,b_i,c_i,d_i\le m1vi1091\le v_i\le 10^9