Tiểu T là một giám định viên chất lượng, hiện đang phụ trách kiểm tra một lô khoáng sản.

Lô khoáng sản này gồm \(n\) viên quặng, đánh số từ \(1\) đến \(n\). Mỗi viên quặng có:

• Khối lượng: \(w_i\)
• Giá trị: \(v_i\)

Quy trình kiểm định được mô tả như sau:

1. Cho \(m\) đoạn kiểm định dạng \([l_i, r_i]\)
2. Chọn một tham số kiểm định \(W\)
3. Với mỗi đoạn \([l_i, r_i]\), tính chỉ số kiểm định \(y_i\) như sau:

\[ y_i = \left( \sum_{j=l_i}^{r_i} [w_j \ge W] \right) \times \left( \sum_{j=l_i}^{r_i} [w_j \ge W] \cdot v_j \right) \]

\([w_j \ge W]\) là giá trị logic: bằng \(1\) nếu đúng, \(0\) nếu sai.

Tổng chỉ số kiểm định toàn lô quặng là:
\[ y = \sum_{i=1}^{m} y_i \]

Nếu \(|y - s|\) quá lớn so với giá trị tiêu chuẩn \(s\) được cung cấp, thì cần kiểm định lại một lô khác.

Tiểu T muốn chọn giá trị \(W\) sao cho sai lệch \(|y - s|\) nhỏ nhất có thể. Bạn hãy giúp anh ta tìm giá trị sai lệch nhỏ nhất.

Định dạng vào

• Dòng đầu tiên: \(n, m, s\)
• Tiếp theo \(n\) dòng: mỗi dòng \(w_i, v_i\)
• Tiếp theo \(m\) dòng: mỗi dòng là một đoạn \([l_i, r_i]\)

Định dạng ra

• Một số nguyên: sai lệch nhỏ nhất \(|y - s|\).

Input

5 3 15 
1 5 
2 5 
3 5 
4 5 
5 5 
1 5 
2 4 
3 3

Output

10

Giải thích

Chọn \(W = 4\), thì:

• Các viên có \(w_j \ge 4\) là viên 4 và 5
• Với mỗi đoạn:
  • [1,5]: có 2 viên hợp → \(2 \times (5 + 5) = 20\)
  • [2,4]: 1 viên hợp → \(1 \times 5 = 5\)
  • [3,3]: không có → \(0\)
• Tổng \(y = 25\)
• Sai lệch với chuẩn \(s=15\) là \(|25 - 15| = 10\)

Ràng buộc

• Với \(10\%\): \(1 \le n, m \le 10\)
• Với \(30\%\): \(1 \le n, m \le 500\)
• Với \(50\%\): \(1 \le n, m \le 5\,000\)
• Với \(70\%\): \(1 \le n, m \le 10\,000\)
• Với \(100\%\):
  • \(1 \le n, m \le 200\,000\)
  • \(0 < w_i, v_i \le 10^6\)
  • \(0 < s \le 10^{12}\)
  • \(1 \le l_i \le r_i \le n\)