Try Lumia 650....recently released in February 2016....runs on Windows 10 Mobile....has all the apps you mentioned above (Facebook, Waze, etc)....price RM999.....battery life (with data plan all day) can last one day at least, still got <20% at night....

Btw, I bought for wife....she's using it....so far so good....

But minimal lag is not guaranteed, especially for a low end Samsung.

ZTE Blade A610
Lenovo Vibe K5

If can spend a bit more, I would recommend Wiko UFeel Lite.

ZTE is a well known Chinese telecommunication brand just like Huawei. Well, ZTE might not be well known here, but it's there. As for Wiko, it's a newcomer French brand. But yeah, since ZTE and Wiko aren't well known here, buying their phones would be a hassle especially in Sabah. To check if it's an original set, it must have the official warranty from the brand itself.

Lenovo Vibe K5 is good enough for light usage, but once your usage gets a little higher, it will definitely lag. As for Huawei and Vivo, their phones in that price range don't support 4G. Unless you can spend a little more, go for Honor 5A. (In case you're wondering, Honor is a sub-brand of Huawei)
https://www.vmall.my/honor-5a

ZTE is a well known Chinese telecommunication brand just like Huawei. Well, ZTE might not be well known here, but it's there. As for Wiko, it's a newcomer French brand. But yeah, since ZTE and Wiko aren't well known here, buying their phones would be a hassle especially in Sabah. To check if it's an original set, it must have the official warranty from the brand itself.

Lenovo Vibe K5 is good enough for light usage, but once your usage gets a little higher, it will definitely lag. As for Huawei and Vivo, their phones in that price range don't support 4G. Unless you can spend a little more, go for Honor 5A. (In case you're wondering, Honor is a sub-brand of Huawei)
https://www.vmall.my/honor-5a

For Xiaomi, I would recommend the Xiaomi Redmi 3S.

To check whether if it's original, here are the ways:
1. The box comes with English text instead of Chinese
2. There's a distributor sticker on the box (usually it's called Thorus)
3. Software comes with many language options instead of only English and Chinese
4. No unknown Chinese apps pre-installed in the phone software
5. Phone comes with Xiaomi Malaysia warranty
As for Meizu M3S, it's not bad at all. But I would go with the Xiaomi Redmi 3S because it's better.

tab a 2016