编程介的小学生 2017-08-24 11:50 采纳率: 20.5%
浏览 609
已采纳

Shoot the Bullet

Gensokyo is a world which exists quietly beside ours, separated by a mystical border. It is a utopia where humans and other beings such as fairies, youkai(phantoms), and gods live peacefully together. Shameimaru Aya is a crow tengu with the ability to manipulate wind who has been in Gensokyo for over 1000 years. She runs the Bunbunmaru News - a newspaper chock-full of rumors, and owns the Bunkachou - her record of interesting observations for Bunbunmaru News articles and pictures of beautiful danmaku(barrange) or cute girls living in Gensokyo. She is the biggest connoisseur of rumors about the girls of Gensokyo among the tengu. Her intelligence gathering abilities are the best in Gensokyo!

During the coming n days, Aya is planning to take many photos of m cute girls living in Gensokyo to write Bunbunmaru News daily and record at least Gx photos of girl x in total in the Bunkachou. At the k-th day, there are Ck targets, Tk1, Tk2, ..., TkCk. The number of photos of target Tki that Aya takes should be in range [Lki, Rki], if less, Aya cannot write an interesting article, if more, the girl will become angry and use her last spell card to attack Aya. What's more, Aya cannot take more than Dk photos at the k-th day. Under these constraints, the more photos, the better.

Aya is not good at solving this complex problem. So she comes to you, an earthling, for help.

Input

There are about 40 cases. Process to the end of file.

Each case begins with two integers 1 <= n <= 365, 1 <= m <= 1000. Then m integers, G1, G2, ..., Gm in range [0, 10000]. Then n days. Each day begins with two integer 1 <= C <= 100, 0 <= D <= 30000. Then C different targets. Each target is described by three integers, 0 <= T < m, 0 <= L <= R <= 100.

Output

For each case, first output the number of photos Aya can take, -1 if it's impossible to satisfy her needing. If there is a best strategy, output the number of photos of each girl Aya should take at each day on separate lines. The output must be in the same order as the input. If there are more than one best strategy, any one will be OK.

Output a blank line after each case.

Sample Input

2 3
12 12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 3 9
1 3 9
2 3 9

2 3
12 12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 0 3
1 3 6
2 6 9

2 3
12 12 12
3 15
0 3 9
1 3 9
2 3 9
3 21
0 0 3
1 3 6
2 6 12

Sample Output

36
6
6
6
6
6
6

36
9
6
3
3
6
9

-1

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-08-27 16:39
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题