Cho ma trận kích thước ~N \times N~, các hàng được đánh số từ ~1~ đến ~N~ từ trên xuống dưới và các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải. Mỗi ô của ma trận mang một giá trị nguyên, ban đầu tất cả các ô đều mang giá trị ~0~.

Thực hiện ~K~ thao tác sau trên ma trận, mỗi thao tác bao gồm ~4~ số nguyên ~r_1,r_2,c_1,c_2~ : tiến hành cộng thêm giá trị ~1~ vào mỗi ô ~(i,j)~ thỏa mãn ~r_1 \le i \le r_2~ và ~c_1 \le j \le c_2~.

Sau khi thực hiện ~K~ thao tác, gọi ~P~ là số ô mang giá trị dương, ~E~ là số ô mang giá trị dương và chẵn, yêu cầu tính ~P \times A + E \times B~, trong đó ~A,B~ là các số nguyên cho trước.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le N \le 10^9~ ; ~1 \le K \le 10^5)~.
• ~K~ dòng tiếp theo, mỗi dòng chứa ~4~ số nguyên ~r_1,r_2,c_1,c_2~ ~(1 \le r_1 \le r_2 \le N~ ; ~1 \le c_1 \le c_2 \le N)~.
• Dòng cuối cùng chứa hai số nguyên ~A~ và ~B~ ~(0 \le A,B \le 1)~.

Output

• In ra giá trị biểu thức cần tính.

Examples

Sample Input 1

4 2
1 3 1 3
3 4 2 4
1 1

Sample Output 1

15

Sample Input 2

4 2
1 3 1 3
3 4 2 4
1 0

Sample Output 2

13

Scoring

• Subtask ~1~ ~-~ ~500~ điểm: ~N,K \le 500~
• Subtask ~2~ ~-~ ~750~ điểm: ~N \le 10^5~ ; ~B=0~
• Subtask ~3~ ~-~ ~750~ điểm: ~B=0~
• Subtask ~4~ ~-~ ~750~ điểm: ~|r_1-r_2|+|c_1-c_2| \le 6~
• Subtask ~5~ ~-~ ~750~ điểm: Không có ràng buộc gì thêm