多方案最低费用查询

题目描述

给定n个一次函数方案和q个整数输入。对每个输入，求所有方案中的最低函数值；若多个方案并列最低，选择编号最小者。

输入格式

第一行输入n、q；接下来n行按编号1至n输入k、b；随后q行各输入一个x。

输出格式

每个查询输出一行最低函数值和对应的最小1-based方案编号。

样例

输入

3 4
20 100
30 40
25 70
0
3
6
10

输出

40 2
130 2
220 1
300 1