31885번 - Yunny's Trip

문제

회윤이는 잠시 휴식을 취하기 위해 자신의 가상 세계인 유니월드에 들어왔다. 유니월드는 무한한 2차원 격자판이고 회윤이는 현재 (0,ドル 0$)에 서있다. 회윤이는 자신의 목적지인 $(E_x, E_y)$에 가기 위하여 다음 2가지 종류의 행동을 반복할 수 있다.

1. 인접한 격자판으로 한 칸 이동한다. 즉 $x$좌표를 1ドル$만큼 변화시키거나 $y$좌표를 1ドル$만큼 변화시킨다. 이 행동은 기력을 1ドル$만큼 소모한다.
2. 회윤이가 들고 있는 아이템을 하나 사용한다. 아이템은 $(a_i, b_i)$ 형태로 주어지며 회윤이의 $x$좌표를 $a_i$만큼, $y$좌표를 $b_i$만큼 증가시킨다. 즉 회윤이의 좌표를 $(x, y)$라고 할 때, 아이템을 사용하였을 시의 좌표는 $(x+a_i, y+b_i)$가 된다. 이 행동은 아이템을 소모하지 않으며 (즉 하나의 아이템을 여러 번 사용할 수 있다), 기력을 2ドル$만큼 소모한다.

회윤이의 기력이 0ドル$ 미만으로 떨어져 버리면 현실 세계로 돌아오게 되므로 회윤이는 기력을 0ドル$ 이상으로 보존하려고 한다. 또한 회윤이는 허약체질이라 초기 기력이 5ドル$를 초과하지 않는다. 회윤이가 목적지에 도달할 수 있는지 구해보자. 또 도착할 수 있으면 그때 소비해야 하는 기력의 최솟값을 구해보자.

입력

첫째 줄에 아이템의 개수 $N$과 회윤이의 초기 기력 $K$가 공백으로 구분되어 주어진다. (1ドル \le N \le 2\times10^5; 1 \le K \le 5$)

둘째 줄부터 $N+1$번째 줄까지 각각의 아이템의 정보 $a_i, b_i$가 공백으로 구분되어 주어진다. $(-10^{12} \le a_i, b_i \le 10^{12})$

마지막 줄에는 회윤이의 목적지 $E_x, E_y$가 공백으로 구분되어 주어진다. $(-10^{12} \le E_x, E_y \le 10^{12})$

아이템과 목적지는 $(0, 0)$이 아니고 동일한 아이템이 중복되어 주어지지 않는다.

출력

회윤이가 소비해야 하는 기력의 최솟값을 출력한다. 만약 회윤이가 $K$의 기력으로 목적지에 도착할 수 없으면 -1을 출력한다.

제한

힌트