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