문제
2차원 평면에 점이 N개 주어진다. i번째 점은 (xi, yi)에 있다. 이 때, 다음 쿼리를 처리하는 프로그램을 작성하자.
a: N개의 점들 중, axi + yi의 최댓값을 출력한다.
입력
첫 번째 줄에 점의 개수를 의미하는 자연수 N과 쿼리의 개수 Q가 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ Q ≤ 500,000)
두 번째 줄부터 N개의 줄에 점의 위치 (xi, yi)가 주어진다. (-109 ≤ xi, yi ≤ 10<9)
그 다음 줄부터 Q개의 줄에 각 쿼리의 aq가 정수로 주어진다. (-109 ≤ aq ≤ 10<9)
출력
각 쿼리에 대해, N개의 점들 중, axi + yi의 최댓값을 출력한다.
예제
5 5
-2 2
-1 1
3 3
5 6
7 -5
-10
-2
0
2
10
22
6
6
16
65
로그인해야 코드를 작성할 수 있어요.