小五准备开始逛商店了，时刻时小五在自己家，有个商店，逛第个商店需要耗费小五的时间（为她开始逛这个商店时的时刻，因为小五会越逛越饿，所以对于任何一个商店，她开始逛的越晚，所需的时间就越长）。小五同一时刻只能逛一个商店，这个商店逛完后，可以前往下一个商店开始逛。
除了逛商店的时间，小五从自己家到任意一个商店，或者从一个商店到另一个商店，都需要花费的时间走过去。
为了追求新鲜感，一个商店小五最多只逛一次，她可以任意安排逛哪些商店以及逛商店的顺序，那么截止到时刻，她最多能逛完多少商店呢？
第一行两个非负整数
接下来行，每行两个非负整数
一行一个非负整数表示小五最多能逛完多少商店
3 7 2 0 3 2 0 3
2
1 3 0 3
0
5 21600 2 14 3 22 1 3 1 10 1 9
5
7 57 0 25 3 10 2 4 5 15 3 22 2 14 1 15
3