THEPOOL - The One-Dimensional Pool Table

A set of N billiard balls are set on a one-dimensional table. The table is 105 meters long, with two pockets at either side. Each ball has zero width and there is no friction so it is moving with a fixed velocity of either left or right and bounces back in a perfect elastic collision from other balls it encounter on its way (or drop into one of the pockets). Your job is to keep track of the balls' movements.

Input

The first number, N, is the number of balls (≤ 105).

This is followed by N pairs of numbers: the distance in meters from the left end of the table and the velocity (positive speed meaning it moves towards right).

The next line tells you which ball you have to track (1 ≤ tracked ball ≤ N).

The last line tells you the time T at which you have to locate the tracked ball.

Note: Each number is on a separate line.

Output

You have to output the position (from the left end) of the tracked ball after time T.

Example 1

Input:
1 
50
1
1
6 Output: 56

Example 2

Input:
2 
95
-1
10
1
1
60 Output:
35

Explanation for Example 2

2 is the number of balls.
One ball is placed at 95 from the left end. It's velocity is -1 (i.e. 1 m/s towards left).
Another ball is at distance 10. Velocity is 1 (i.e. towards right).
The first ball from left end is to be tracked. (i.e. ball at distance 10 from left end).
You need to find the new position of the tracked ball at time t=60s.


Added by:Vishrut Patel
Date:2012-10-09
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IEEE Xtreme 5.0

hide comments
2018-12-27 05:01:34
FYI, speed*T fits into int
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.