当前没有测试数据。

题目描述

一年一度的双十一剁手节又来临了，小瑶今年给自己规定最多只花m元去购物，超出就剁手！他看中了n件物品，每件物品只会买一件，每件物品的价格为a，他对每件品都有一个价值认同度b，为了防止剁手，小瑶想把每种可能引起剁手风险的方案给找出来！有剁手风险的方案是指再多买任意一件物品都会超出m元！同时还要找出所有可行方案中价值认同度最高是多少？

输入格式

第一行两个数m, n，分别表示钱数和物品数量。

第二行n个数，表示每件物品的价格。

第三行n个数，表示每件物品的价值认同度。

输出格式

第一行一个数，表示有剁手风险的方案数。由于方案数可能太多，只需要输出方案数模9****98244353 即可 。

第二行一个数，表示可行方案中价值认同度最高值。

样例

95 2
4 15 
7 33

0
40

解释#1

显然两件物品都购买也没有任何风险，故输出风险方案数为0，价值认同度为40。

73 3
28 63 53 
48 54 29

3
54

解释#2

购买任何一件物品后都不能再购买其它物品，所以三种购买方案都是风险方案，最大价值认可度为购买第2件物品，即为54。

数据范围

对于20%的数据，n≤10，m≤100。

对于另外20%的数据，所有物品的价格总和=m+1。

对于另外30%的数据，n≤300；

对于100%的数据，n,m≤5000，1≤ai≤1000，0≤bi≤10^6。